BOJ 2178 - 미로 탐색
알고리즘/DFS∕BFS문제
간단한 BFS를 이용한 길 찾기 문제이다. 알고리즘 분류는 BFS로 되어있는데 당연히 DFS로도 된다. 나는 BFS로 구현했다.
소스
#include <iostream> #include <queue> using namespace std; struct pt{ int x; int y; }; int map[501][101] = {0}; int visit[501][101] = {0}; queue<pt> q; void setVisit(int x, int y, pt o){ pt next; next.x = x; next.y = y; q.push(next); visit[y][x]+=visit[o.y][o.x]+1; } int main(){ int n,m,i,j;char c; pt o; cin>>n>>m; for(i=0;i<n;i++){ for(j=0;j<m;j++) { cin >> c; map[i][j]=c-'0'; } } o.x=0;o.y=0; q.push(o); visit[0][0]=1; while(!q.empty()){ pt front = q.front(); q.pop(); if(front.x-1 >= 0 && !visit[front.y][front.x-1] && map[front.y][front.x-1]) setVisit(front.x-1,front.y,front); if(front.x+1 < m && !visit[front.y][front.x+1] && map[front.y][front.x+1]) setVisit(front.x+1,front.y,front); if(front.y-1 >= 0 && !visit[front.y-1][front.x] && map[front.y-1][front.x]) setVisit(front.x,front.y-1,front); if(front.y+1 < n && !visit[front.y+1][front.x] && map[front.y+1][front.x]) setVisit(front.x,front.y+1,front); } cout << visit[n-1][m-1] << '\n'; }
각 줄마다 띄어쓰기 없이 미로가 주어지므로 char 형으로 받은 다음 '0'(48)을 빼주어 정수형으로 바꾸어주었다.
큐에는 이번에 탐색해야할 좌표 값을 저장해야하므로 x,y값을 가지는 구조체를 만들어 좌표값을 저장시켜 주었고 맨 처음 시작할때 0,0 좌표 변수를 만들어 큐에 넣어주고 시작하게 했다.
탐색을 할때 상하좌우에 이동 할 수 있으며 방문하지 않은곳이 있다면 방문을 했다는 표시를 하고(어차피 큐에 넣고 나중에 방문할것이니 미리 표시해도 상관이 없다) visit[y][x]변수에 몇 번 이도해서 x,y 좌표에 왔는지에 대한 횟수를 적어두게하였다.