미로 탐색

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	192 MB	146493	63731	40916	42.227%

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

다음 N개의 줄에는 M개의 정수로 미로가 주어진다.

각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.

항상 도착 위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1

15

예제 입력 2

4 6
110110
110110
111111
111101

예제 출력 2

9

예제 입력 3

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

38

예제 입력 4

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

13

출처

• 데이터를 추가한 사람: djm03178, jh05013, poia0304, sait2000

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

입력 확인 코드

문제에서 ‘각각의 수들은 붙어서 입력으로 주어진다.’

이 부분은 string 으로 입력을 받고 string의 인덱스를 순회하면서 맵 배열에 넣어 주었다.

#include <iostream>

using namespace std;

string str;

int N, M;

int map[101][101];

bool debug = true;

int main()
{
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		
		cin >> str;

		for (int j = 0; j < M; j++) map[i][j + 1] = str[j] - '0'; // char -> int
	}


	if (debug) {

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {

				cout << map[i][j] << " ";
			}

			cout << "\n";
		}
	}



	return 0;
}

디버깅

통과된 코드

#include <iostream>
#include <queue>

using namespace std;

string str;

int N, M, dx, dy;

// 처음 방문시에는 갈 수 있는지 없는지 확인(0, 1)
// 방문한 다음에는 몇번쨰로 방문 했는지 기록
int map[101][101];

// 해당 좌표에 방문을 했는지 체크
bool checkMap[101][101];

// 탐색하는 방향 설정 =>  상, 하 ,좌 ,우
int dxdy[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

// BFS를 위한 Queue
queue<pair<int, int>> myQueue;

pair<int, int> tempPair;

// 디버그용 bool
bool debug = false;

int main()
{
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {

		cin >> str; // 입력을 문자열 자체로 받음

		// string 의 인덱스를 이용하여 map에 마킹
		// char -> int
		for (int j = 0; j < M; j++) map[i][j + 1] = str[j] - '0';
	}


	// BFS를 시작하기위한 초기값 설정
	checkMap[1][1] = true;
	map[1][1] = 1; // 카운트
	myQueue.push(make_pair(1, 1));

	while (!myQueue.empty()) {

		tempPair = myQueue.front();
		myQueue.pop();

		// 상/하/좌/우를 탐색하기 위한 반복문
		for (int i = 0; i < 4; i++) {

			dx = tempPair.first + dxdy[i][0];
			dy = tempPair.second + dxdy[i][1];

			// 문제의 범위를 벗어나는 경우 => 넘어간다.
			if (dx == 0 || dy == 0 || dx > N || dy > M) continue;

			// '0' 이동할 수 없는 칸 인 경우, 이미 방문한 곳 일 경우 => 넘어간다.
			if (map[dx][dy] == 0 || checkMap[dx][dy] == true) continue;

			map[dx][dy] = map[tempPair.first][tempPair.second] + 1; // 카운트를 올려준다.
			checkMap[dx][dy] = true; // 방문처리
			myQueue.push(make_pair(dx, dy));

			if (dx == N && dy == M) { // 목적지에 도달했다면 중지

				// 외부 	while (!myQueue.empty())을 나가기 위해서
				// Queue를 비워준다.
				while (!myQueue.empty()) myQueue.pop(); 

				break;
			}
		}
	}

	// 정답 출력(해당 위치에 도달하기위한 최소)
	cout << map[N][M];



	if (debug) { // 시각적 디버그용 코드
		cout << "\n";
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cout << map[i][j] << " ";
			}
			cout << "\n";
		}
	}



	return 0;
}