[Python][C++] 2178번 미로 탐색

문제

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

 

 

코드

1. Python

import sys
from collections import deque

input = sys.stdin.readline

def bfs(x, y):
    graph[x][y] = 1
    d = deque()
    d.append((x, y))
    
    while d:
        x, y = d.popleft()  # 현재 위치를 덱에서 꺼냄
        for i in range(4):  # 네 방향으로 탐색
            nx = x + dx[i]
            ny = y + dy[i]
            # 새로운 위치가 보드 범위 밖이면 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            # 새로운 위치가 '1'이고 아직 방문하지 않았으면
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1  # 새로운 위치까지의 거리 갱신
                d.append((nx, ny))  # 새로운 위치를 덱에 추가
    return graph[n-1][m-1]  # 도착 지점 (n-1, m-1)까지의 거리 반환

n, m = map(int, input().split())

graph = [[0] * m for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j in range(m):
        if s[j] == '1':
            graph[i][j] = 1

# 방향 벡터 (상, 하, 좌, 우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

print(bfs(0, 0))

 

2. C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<string> board;

// BFS를 수행하는 함수
void bfs(int n, int m) {
	int x = 0, y = 0; // 시작 위치는 좌상단 (0, 0)
	queue<pair<int, int>> q;
	vector<vector<int>> visited(n, vector<int>(m));
	int dx[4] = { -1, 1, 0, 0 }; // x 방향으로의 이동 (위, 아래)
	int dy[4] = { 0, 0, -1, 1 }; // y 방향으로의 이동 (왼쪽, 오른쪽)

	q.push({ x, y });
	visited[x][y] = 1;

	// BFS 루프
	while (!q.empty()) {
		x = q.front().first; // 현재 위치의 x 좌표 가져오기
		y = q.front().second; // 현재 위치의 y 좌표 가져오기
		q.pop(); // 현재 위치를 큐에서 제거

		// 네 방향으로 탐색
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; // 새로운 x 좌표
			int ny = y + dy[i]; // 새로운 y 좌표

			// 새로운 위치가 보드 범위 내에 있고, '1'이며 방문하지 않았으면
			if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
				board[nx][ny] == '1' && !visited[nx][ny]) {
				q.push({ nx, ny }); // 새로운 위치를 큐에 추가
				visited[nx][ny] = visited[x][y] + 1; // 새로운 위치를 방문했다고 표시하고 거리 갱신
			}
		}
	}

	// 도착 지점 (n-1, m-1)까지의 거리를 출력
	cout << visited[n - 1][m - 1];
}

int main() {
	int n, m;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		board.emplace_back(temp);
	}

	bfs(n, m);

	return 0;
}

 

풀이 

2차원 배열에서 사용하는 BFS 알고리즘의 가장 기본 문제다. 더 높은 난이도의 BFS문제들은 이 문제를 변형시킨 문제들이 대부분이다.

 

 

1. 시작점을 큐에 넣고 시작
2. 큐에서 현재 위치를 꺼내 네 방향(상하좌우)을 확인
3. 이동 가능한 칸(즉, 값이 '1'인 칸)으로 이동하고 그 칸을 방문 표시
4. 이동할 때마다 거리를 1씩 증가
5. 도착점에 도달하면 그때의 거리를 출력

 

BFS 알고리즘 참고

 

https://ehdbs0903.tistory.com/entry/Algorithm-너비-우선-탐색-BFSBreadth-First-Search-알고리즘

[Algorithm] 너비 우선 탐색 / BFS(Breadth-First Search) 알고리즘