[백준 2178] 미로 탐색 (C++/Python)

C++)

#include <iostream>
#include <queue>
#define MAX_NUM 102

using namespace std;

char arr[MAX_NUM][MAX_NUM];
int visited[MAX_NUM][MAX_NUM];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> q;

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}

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

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

			if (arr[nx][ny] == '1' && visited[nx][ny] == 0) {
				q.push({ nx,ny });
				visited[nx][ny] = visited[x][y] + 1;
			}
		}
	}

	cout << visited[n - 1][m - 1];

	return 0;
}

 

 

 

Python)

import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

n, m = map(int, read().rstrip().split())
arr = [''] * n
visited = [ [-1] * m for _ in range(n) ]

for i in range(n):
    arr[i] = list(map(int, read().rstrip()))

visited[0][0] = 1
q.append((0,0))

while q:
    x, y = q.popleft()

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue

        if arr[nx][ny] == 1 and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            q.append((nx,ny))
            
print(visited[n-1][m-1])