[백준] 2178 미로 탐색(Java, Python)

백준 - 2178 미로 탐색

풀이

1. bfs
2. 갈 수 있는 좌표(값이 1인 좌표)에 지나가는 칸 수를 저장
3. 상하좌우로 움직이는 것 -> dx, dy

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

nx = x + dx[i]
ny = y + dy[i]

graph[ny][nx] ➡️ graph[y][x]로부터의 상하좌우를 구할 수 있음

삽질

시간초과 이슈

1. scanner ➡️ BufferReader 입력을 더 빠르게 처리함
2. visited 배열과 distance 배열을 만들어서 유효한 값에 접근하게 만들었는데 시간초과가 나서 수정
   ✔️ visited -> graph[i][j] 값이 1인 것만 방문하도록
   ✔️ distance -> graph[i][j] 값을 바로 수정해서 지나온 칸 수를 저장

코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Maze {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String size = br.readLine();
		StringTokenizer st = new StringTokenizer(size);
		int col = Integer.parseInt(st.nextToken());
		int row = Integer.parseInt(st.nextToken());
		int[][] graph = new int[col][row];
		for (int i = 0; i < col; i++) {
			String[] lineNum = br.readLine().split("");
			for (int j = 0; j < row; j++) {
				graph[i][j] = Integer.parseInt(lineNum[j]);
			}
		}
		System.out.println(bfs(graph, col, row));
	}

	private static int bfs(int[][] graph, int col, int row) {
		List<int[]> queue = new ArrayList<>();
		int[] dx = {-1, 1, 0, 0};
		int[] dy = {0, 0, -1, 1};

		queue.add(new int[]{0, 0});
		while (queue.size() > 0) {
			int[] vertex = queue.remove(0);
			int y = vertex[0];
			int x = vertex[1];
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < row && ny >= 0 && ny < col && graph[ny][nx] == 1) {
					queue.add(new int[]{ny, nx});
					graph[ny][nx] = graph[y][x] + 1;
					if (ny == col - 1 && nx == row - 1) break;
				}
			}
		}
		return graph[col - 1][row - 1];
	}
}

Python

from collections import deque
from sys import stdin

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    queue = deque([(0, 0)])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    
N, M = map(int, stdin.readline().split())
graph = [list(map(int, stdin.readline()[:-1])) for _ in range(N)]

bfs()

print(graph[N - 1][M - 1])