백준 알고리즘 2178 (미로 탐색) - C++, Python

[문제] 백준 알고리즘 2178 (미로 탐색)

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

2178번: 미로 탐색

 

전형적인 BFS 미로탐색 문제이다.

그래서 Queue와 while문, 방문 여부를 활용한다.

매번 느끼는 거지만, C++은 압도적으로 빠르다.....

 

1. N, M, 미로 Map을 받는다.

2. (0,0)부터 움직이며 다음 nx, ny가 범위를 벗어나지 않는지 확인

3. Map에 값이 0이 아니고 방문하지 않았으면, Map에 이전 값을 누적한다.

4. 동시에 queue에 append 해준다.

5. Map 끝에 도달하면 최종 누적 출력

 

아래와 같은 Map은,            

1	1	0	1	1	0
1	1	0	1	1	0
1	1	1	1	1	1
1	1	1	1	0	1

누적 후에 이렇게 된다.

1	2	0	8	9	0
2	3	0	7	8	0
3	4	5	6	7	8
4	5	6	7	0	9

 

[C++]

#include <cstdio>
#include <queue>
#include <cstring> // memset
using namespace std;
int n, m;
int map[101][101];
bool visited[101][101];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

void solve_bfs(int x, int y) {
	queue< pair<int, int> > q;
	q.push({x, y});
	visited[x][y] = 1;
	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		if (x == n - 1 && y == m - 1) {
			printf("%d\n", map[x][y]);
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx, ny;
			nx = x + dx[i];
			ny = y + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (map[nx][ny] && !visited[nx][ny]) {
					visited[nx][ny] = 1;
					map[nx][ny] = map[x][y] + 1;
					q.push({nx, ny});
				}
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	solve_bfs(0, 0);
	return 0;
}

 

[Python]

import sys
n, m = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
queue = []
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

def solve_bfs(x, y):
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.pop(0)
        if x == n-1 and y == m-1:
            return
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if board[nx][ny] and not visited[nx][ny]:
                    visited[nx][ny] = True
                    board[nx][ny] = board[x][y] + 1
                    queue.append((nx, ny))
solve_bfs(0,0)
for i in range(n):
    print(board[i])
print(board[-1][-1])