백트래킹을 공부하기 전에 BFS와 재귀를 꼭 꼭 먼저 공부하는 것을 추천합니다. 구현의 상당 부분이 재귀로 이루어지고 BFS와 비슷한 이론의 느낌이 나기 때문입니다. [알고리즘] BFS와 DFS BFS는 큐를 이용한 탐색의 한 방법으로, 너비 우선 탐색이다. 너비 우선 탐색이라고 하면 감이 잘 안 올 텐데, 알고리즘부터 보자. 큐에 시작점을 push 한다. 큐의 front를 저장해 두고 pop 한다. pop한 jun-n.tistory.com [알고리즘] 재귀 - 귀납적 사고와 재귀 함수 구조 짜기 문제를 재귀 방식으로 푼다는 것은 귀납적 방식으로 문제를 해결하겠다는 것이다. 이 마인드가 상당히 중요한데, 재귀 문제를 일반 문제 풀듯이 절차 지향적으로 이해하면 안 된다. 예를 들어 1~ jun-n.tist..

1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 예제 1 4 4 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 ans : 4 2 5 2 0 0 1 1 0 0 0 1 1 0 ans : -1 이 문제를 풀기 전에 아래의 벽 부수고 이동하기 문제를 꼭 꼭 먼저 푸는 것을 추천한다. 내가 떠올린 풀이가 아래 문제와 99% 비슷하기 때문이다. [BOJ] C++ 2206 벽 부수고 이동하기 - BFS 활용 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 예제 5 17 res : 2 처음에 떠올린 풀이는 순간 이동이 한 번에 한 번만 가능한 줄 알고 +- 한 칸과 순간이동 한 것까지 큐에 넣어서 bfs를 돌렸다. 이렇게 구현하면 주의점이 방문 조건을 체크할 때 이미 방문한 것도 다시 방문해서 최단거리로 체크해야 했다. 이 부분 때문에 틀리는 줄 알고 찾아보니 가중치가 0, 1 밖에 없는 그래프 탐색을 위한 0-1 BFS 알고리즘이 있었는데, 내가 구현한 것과 얼추 비슷해서 맞는..

2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 예제 10 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 ans : 3 먼저 bfs를 통해 섬에 번호를 매겨줄 필요성을 느꼈다. 어떤 풀이를 쓰던 무조건 섬끼리..

4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 4 4 #### #JF# #..# #..# ans : 3 전에 푼 토마토 문제와 비슷한 느낌이지만 굉장히 다르다. 불과 지훈이가 동시에 BFS를 돌리면 될 것 같지만 사실 무조건 불부터 돌려야 한다. 같은 시간대에 불이 도달할 수 있으면 지훈이는 해당 칸에 못 가기 때문이다. 동시에 돌리는 것처럼 큐 한 개로 처리하면 우선순위를 고려하기 굉장히 번거롭고 오래 걸린다. 따라서 불부터 BFS를 돌리고, 지훈이 도착시간이 불보다 작으면 방문 가능한 칸..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 예제 6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ans : 8 최단 경로를 보고 바로 BFS를 떠올렸다. 조금 다른 점은 토마토가 여러 개인 경우 동시에 여러 시작점에서 BFS를 시작해야 한다는 것이다. 토마토들 간의 우선순위는 없으니 간단하게 큐에 시작점을 모두 넣고 BFS를 돌리면 된다. 구현은 전에 푼 문제와 거의 똑같다. 조금 다른건 토마토가 없는 칸, 즉 다른 문제의 벽에 해당하는 칸만 ..