본문 바로가기

너비우선탐색

(2)
[백준] 2002 - 벽 부수고 이동하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 너비우선 탐색(BFS)로 풀어야 하는 문제다. '벽을 최소 1회는 뚥을수 있다'는 조건이 문제를 어렵게 만드는데, 이부분은 벽을 최소 1회 뚥었는지, 안뚥었는지에 대한 조건 여부를 방문 여부에 차이를 두고 기록해야한다. #include #include using namespace std; #include typedef struct _loc { int y; int x; int distan..
[백준] 10026 - 적록색약 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 위 문제는 순수 BFS(너비우선 탐색)와 DFS(깊이우선탐색) 두가지 모두로 해결이 가능하다. 색약의 경우만 R, G중 하나를 R 혹은 G로 모두 변경 후에 다시 BFS, DFS를 돌리면 색상의 구역을 구분할 수 있다. 아래 코드는 BFS, DFS 모두를 구현한 정답이다. 직장내 SW 검정이 있어 멘토링을 하느라 두가지 방식 모두 구현하였다. 아래 코드에서 관심있게 볼 포인트는 BFS는 Queue, DF..