BOJ 2178 - 미로 탐색

• 붙어있는 숫자로 입력이 주어진다. 입력을 받고 BFS를 돌리면 된다.

문제 풀이

소스코드

#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<utility>
using namespace std;

int di[4]={-1, 0, 1, 0},  dj[4]={0, 1, 0, -1};

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	vector<vector<int>> maze(n+2, vector<int>(m+2, 0)), visited(n+2, vector<int>(m+2, 0));
	for(int i=1;i<=n;i++){
		string s;
		getline(cin, s);
		while(s=="\0") getline(cin, s);
		for(int j=1;j<=s.length();j++) maze[i][j]=s[j-1]-'0';
	}
	queue<pair<int, int>> q;
	q.push(make_pair(1001, 1));
	visited[1][1]=1;
	while(!q.empty()){
		int ci=q.front().first/1000, cj=q.front().first%1000, pcnt=q.front().second;
		for(int i=0;i<4;i++){
			int ni=ci+di[i], nj=cj+dj[i];
			if(maze[ni][nj] && visited[ni][nj]==0){
				if(ni==n && nj==m){
					printf("%d", pcnt+1);
					return 0;
				}
				q.push(make_pair(ni*1000+nj, pcnt+1));
				visited[ni][nj]=1;
			}
		}
		q.pop();
	}
}

풀고나서

• 입력을 string으로 처리해서 헤맸다. 항상 스트링 처리만 나오면 정신없어진다. 풀고나서 다른 코드들을 봤는데 기가막힌 것을 찾았다. scanf의 포맷에서 지원되는 기능인데 scanf("%1d", &m[i][j])가 가능하다는 것이다. 다른 타입에 대해서는 모르겠지만 정수라도 되는게 어디냐,,,

• DFS를 돌리면 도착지점에 도달할 때마다 하나하나 경로길이를 저장해놓아야 하지만 BFS를 이용하면 처음 도착지점에 도달할 때 프로그램을 종료시키면 된다. 이 문제에서는 입력이 100x100이라 상관없지만 입력이 커지면 BFS가 훨씬 효율적일 것이다.