백준 2178 : 미로 탐색

https://www.acmicpc.net/problem/2178

1. 접근

• 최단 경로를 찾아야하므로, BFS를 사용해야 한다. (DFS의 경우, 처음 찾게된 경로로만 탐색하게 되므로 최단경로라는 보장이 없다.)
• 입력을 붙여서 받기 때문에 char 배열에 문자 하나씩 입력받고 한 칸씩 graph 배열로 옮겨준다.
• 배열의 시작은 0부터, 문제의 좌표는 1부터 시작이므로 값 차이를 반영해야 한다
• 여러 경로를 진행하여 최솟값을 찾아야 한다.
• queue에 cnt값을 함께 전달하고, 그 값에서 하나 늘리는 방식으로 구현한다.
  (경로를 여러개 동시진행하므로, 공동의 변수를 사용하면 결과값이 이상해진다. 토마토 문제 참고.)
• 주의사항 정리글 https://www.acmicpc.net/board/view/25832

2.나의 풀이

#include <iostream>
#include <queue>
#define MAX 101
using namespace std;

int n, m;
int graph[MAX][MAX];
int dx[4] = { -1,1,0,0 };//상하좌우
int dy[4] = { 0,0,-1,1 };
bool visited[MAX][MAX];
int ret = 0;
queue<pair<pair<int, int>,int>> q; //<좌표값,cnt> 

void bfs(int x, int y, int cnt) {
	q.push(make_pair(make_pair(x, y),cnt));
	visited[x][y] = true;

	int nx, ny;
	while (!q.empty()) {
		x = q.front().first.first;
		y = q.front().first.second;
		cnt=q.front().second+1;
		//cout << "(" << x << "," << y << "), cnt :: " << cnt << "\n";
		q.pop();

		if (x == n - 1 && y == m - 1) { //도착 판정
			if (ret == 0) ret = cnt; 
			else if (ret > cnt) ret = cnt; //최솟값을 택함
			return;
		}

		for (int i = 0; i < 4; i++) {
			nx = x + dx[i];
			ny = y + dy[i];
			if (nx >= 0 && nx < n&&ny >= 0 && ny < m) { //범위 내에 있고
				if (graph[nx][ny] == 1 && !visited[nx][ny]) { //이동할 수 있으며 아직 방문한 적 없다면
					q.push(make_pair(make_pair(nx, ny),cnt)); //좌표값과 cnt 값 페어로 push
					visited[nx][ny] = true;
				}
			}
		}

	}
}

int main() {
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		char tem[MAX]; //문자열로 입력받기
		cin >> tem;
		for (int j = 0; j < m; j++) {
			graph[i][j] = tem[j] - '0'; //숫자로 graph 배열에 저장
		}
	}

	bfs(0, 0,0);

	cout << ret << "\n";
	return 0;

}