그래프 탐색17

• 

  [프로그래머스] 리코쳇 로봇 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: 일반적인 BFS 문제와 비슷하지만 조금 다른 부분은 보드를 한 칸씩 이동하는 것이 아닌 미끄러져 움직이는 것을 구현하는 부분이었다. 아이디어도 어렵지 않았는데 이상하게 코드로 옮기면 종료 조건을 찾지 못해서 무한 루프를 돌았다. 결국 구글링을 통해서 내 코드에서 부족한 부분을 채워서 제출했더니 문제를 해결할 수 있었다. 알고리즘 .. 알고리즘 문제 풀이: 파이썬/Programmers 2023. 11. 15.

• 

  [프로그래머스] 무인도 여행 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: 전형적인 그래프 탐색 문제이다. 이런 유형은 많이 풀어서 그냥 읽자마자 풀이가 떠오르는 것 같다. 파이썬으로 알고리즘 문제를 풀 때 함수 안에 함수를 중첩해서 정의하는 코드를 별로 좋아하지 않는다. 왜냐하면 코드를 읽으면서 함수의 흐름을 따라가다가 갑자기 다른 함수의 정의 부분이 나오는 것이 어색하다고 생각한다. 함수는 각각 정의.. 알고리즘 문제 풀이: 파이썬/Programmers 2023. 11. 7.

• 

  [BOJ_7576] 토마토 📌 문제 링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 같은 유형의 실버 문제를 몇 문제 풀고 나서 도전해 보니 골드 난이도의 문제도 어렵지 않게 풀 수 있었다. 유형별로 문제를 풀면서 난이도를 높여가는 방법으로 연습을 해봐야겠다. 위 문제에서는 기존 배열(grid)의 값을 수정하면서 탐색을 진행하기 때문에 굳이 visited 배열을 이용해서 방문 여부를 확인할 필요가 .. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 2.

• 

  [BOJ_1743] 음식물 피하기 📌 문제 링크: https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 아직 방문하지 않은 음식물을 만날 때마다 너비 우선 탐색을 이용하여 상하좌우를 탐색한다. 탐색을 계속해서 진행한다는 것은 음식물을 만난다는 의미이므로 그때마다 크기가 음식물의 크기를 업데이트시킨다. 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 2.

• 

  [BOJ_11123] 양 한마리... 양 두마리... 📌 문제 링크: https://www.acmicpc.net/problem/11123 11123번: 양 한마리... 양 두마리... 얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지. 그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!" www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: - 쉬운 그래프 탐색 문제였다. 해당 유형의 풀이법을 잊지 않게 자주 풀어봐야겠다. - 2차원 배열관련 문제를 풀 때 변수 이름을 map으로 설정하지 않게 주의하자! 알고리즘 문제 풀이: 파이썬/BOJ 2023. 10. 1.

• 

  [BOJ_1926] 그림 📌 문제 링크: https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 꽤 오랜만에 풀어본 그래프 탐색 문제였지만 기존 코드를 참조하지 않고 기억에만 의존해서 문제를 해결했다. 매번 그래프 탐색 문제를 풀 때 DFS, BFS 코드 템플릿이 기억나지 않아서 기존에 내가 풀어둔 코드를 참고하곤 했는데, 오늘은 참고 없이 해결한 것으로 보아 그동안의 문제 풀이 경험이 조금은 쌓였다는 생각이 든다. 이 문제에서 주.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 10.

• 

  [BOJ_25689] 안전 영역 📌 문제 링크: https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 지역을 나타내는 2차원 배열 arr에 대해서 높이에 따른 물에 잠기지 않는 영역을 모두 확인해주면 되는 문제이다. 문제의 입력 조건에서 높이는 1부터 100 이하의 정수라고 적혀 있지만, 해당 범위만 확인하도록 코드를 작성하면 약 70% 정도에서 문제를 틀리게 될 것이다. 문제의 하단을 확인해보면 노트에 '아무 지역도 물에 잠기지 않을 수.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 10. 23.

• 

  [BOJ_16953] A -> B 📌 문제 링크: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net ❌ 내 풀이(Failure) : ✅ 내 풀이(Success) : 🧐 Review: BFS를 이용해서 풀이를 구현하는 것은 어렵지 않았고, 주어진 테스트 케이스도 모두 통과해서 제출했지만 메모리 초과가 발생했다. 그래서 문제를 다시 읽어보니 입력 값으로 주어지는 a와 b의 값이 최대 10억으로 정말 큰 수였다. 그래서 b의 값을 이용해 배열을 선언한다면 메모리 초과가 발생할 수밖에 없었다. 그래도 혹시 모르니까 기존의 풀이에서 배열을 1개만 사용하도록 변경했지만 여전히 메모리 초과가 발생했다. 따라서 b의 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 20.

• 

  [BOJ_4963] 섬의 개수 📌 문제 링크: https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 가장 최근에 풀었던 그래프 탐색문제들을 모두 bfs로 풀어서 dfs로 문제를 풀려고 하니 조건들을 어떤 순서로 배치해야할지 꽤 고민을 했었다. 알고 있는 풀이법이라고 해도 지속적으로 연습하지 않는다면 알면서도 풀지 못하는 경우가 생길 수 있음을 깨닫게 해준 문제였다. 또, 2차원 배열관련 문제를 풀때는 x, y 좌표를 잘 확인.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 15.

• 

  [BOJ_7562] 나이트의 이동 📌 문제 링크: https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 방향벡터를 이용해서 나이트가 이동해야 하는 좌표를 어떻게 나타내는지에 따라서 bfs 안의 코드를 좀 더 깔끔하게 표현할 수 있다. x와 y의 좌표가 이동할 수 있는 좌표를 서로 다른 리스트에 저장하기 보다 위의 코드처럼 하나의 좌표쌍으로 표현해보면 어떨까? 🚩 Idea: - "너 BFS를 이용해서 특정 좌표를 찾아갈 수 있니?"라고 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 14.