# 백준 : 미로 탐색(2178) - DFS
문제
https://www.acmicpc.net/problem/2178소스
(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_2178_fastestway_DFS)#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
using namespace std;
int map[100][100];
int max_x;
int max_y;
int minimum = 0;
void find_DFS(int x, int y, int result) {
if((x == max_x - 1) && (y == max_y -1)) {
if(minimum > result) minimum = result;
return;
}
map[y][x] = 0;
// find up
if((y > 0) && map[y-1][x]) find_DFS(x, y-1, result + 1);
// find down
if((y < max_y - 1) && map[y+1][x]) find_DFS(x, y+1, result + 1);
// find left
if((x > 0) && map[y][x-1]) find_DFS(x-1, y, result + 1);
// find right
if((x < max_x -1) && map[y][x+1]) find_DFS(x+1, y, result + 1);
map[y][x] = 1;
}
int main(void) {
string input;
cin>>max_y>>max_x;
minimum = max_x * max_y;
for(int i=0; i<max_y; i++) {
cin>>input;
for(int j=0; j<max_x; j++) {
map[i][j] = input.at(j) - 48;
}
}
find_DFS(0, 0, 1);
cout<<minimum;
}
풀이
미로 찾기 문제는 가장 전형적인 DFS 또는 BFS를 사용해서 푸는 알고리즘이다.우선 전체 길을 만들어주기 위해 1 또는 0으로 갈 수 있는 길인지의 여부를 작성하였고, 그 이후에 각각의 상황에 따른 미로 찾기를 진행하였다.
상황은 총 4가지로 구성된다.
1. 위로 올라갈 수 있는 경우
2. 아래로 내려갈 수 있는 경우
3. 왼쪽으로 갈 수 있는 경우
4. 오른쪽으로 갈 수 있는 경우
각각의 상황에 대해서는 다음과 같은 조건을 부여할 수 있다.
1. 위로 올라가려면, 현재 있는 곳이 가장 위가 아니어야 한다 (y > 0)
2. 아래로 내려가려면, 현재 있는 곳이 가장 밑이 아니어야 한다 (y < MAX - 1)
3. 왼쪽으로 가려면, 현재 있는 곳이 가장 왼쪽이 아니어야 한다 (x > 0)
4. 오른쪽으로 가려면, 현재 있는 곳이 가장 오른쪽이 아니어야 한다 (x < MAX - 1)
각각의 경우에 따른 if문을 작성해주면 되는데, 중요한 부분은 두가지가 있다.
1. 미로의 맨 마지막 부분까지 갔을 때, 최단 거리를 측정해주는 기준은 "모든 부분을 다 돌았을 경우의 수 보다 작은 경우에는 무조건 그 값이 최단 거리"라는 것을 보여야 한다.
2. 현재 시점을 기준으로 확인을 진행할 때에는 "현재 시점을 밟고 있다"는 표시를 위해 잠시 스위치를 꺼두는(값을 0으로 해주는) 작업을 진행하고, 모든 if문을 진행하여 상하좌우를 확인하고 나면, 다시 스위치를 켜두는(값을 1로 해주는) 작업으로 다시 이 곳을 확인해도 좋다는 표시를 해야한다. 일종의 '동기화(synchronization)'과 같은 작업이라고 느낀다.
문제는 이 문제를 '틀렸다'는 것이다.. 시간 초과가 발생했는데.
왜 그런지 하고 찾다가 한가지 해결 방법을 확인했다.
쉬운 DFS로 풀어보려했더니 오류가 났다.
다음 포스팅에서 BFS로 한번 풀어보도록 하겠다.
댓글
댓글 쓰기