본문 바로가기

BFS

(4)
[백준] 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..
[백준] 1039 - 교환 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 처음엔 문제를 읽고 '연산을 K번 할 수 없다' 라는 의미가 뭔지를 이해하지 못해 한참 생각을 했다. 주어진 정수의 각 자리수를 바꿀때 자리수가 짧으면 K번을 교환할 수 없는 경우가 생긴다. 이에 대한 처리를 해줘야 하는데 K번의 최대값이 10이므로 BFS를 통한 완전 탐색이 가능할 것 같았다. 구현시 유의할 점은 다음과 같다. K번을 바꾼 뒤의 정수가 최대값이어야 하며, 바꾼 과정에서의 최대값은 의미가 없다. BFS로 Queue에서 Push시에 바꾼 정수의 앞자리가..
[백준] 3055 - 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치�� www.acmicpc.net 자료구조인 Queue와 BFS(너비우선 탐색)에 대한 이해가 필요한 문제다. 물이 차오르는 것과, 고슴도치가 이동하는 것 두가지에 모두 BFS를 적용할 수 있지만 나는 별생각 없이 고슴도치의 이동에 대해서만 BFS를 적용하였고, 물이 차오르는 것은 무식하게 for문을 돌렸다. 그럼에도 pass는 나온다. 처음엔 완전탐색으로 DFS(깊이 우선 탐색)을 해보았으나 시간초과가 나온다. 이미 갔던 곳에 대해 필터..