작성 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class maze_search_2178 {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n : 세로, m : 가로
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] maze = new int[n][m];
        for(int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++){
                // char => string => int
                maze[i][j] = Integer.parseInt(Character.toString(line.charAt(j)));
            }
        }

        // 방문처리
        int[][] dist = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dist[i][j] = -1;
            }
        }

        // 큐 => 시작 지점 넣고 => 시작 지점 0으로 방문 처리
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        dist[0][0] = 1;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[1];
            int y = current[0];

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

                if (nx >= 0 && nx < m && ny >= 0 && ny < n && maze[ny][nx] == 1 && dist[ny][nx] == -1) {
                    queue.offer(new int[]{ny, nx});
                    dist[ny][nx] = dist[y][x] + 1;
                }
            }
        }

        System.out.println(dist[n-1][m-1]);
    }
}

설명

자료구조 및 로직

해당 코드는 주어진 미로에서 출발점(0, 0)부터 도착점(n-1, m-1)까지의 최단 경로 길이를 찾는 BFS(Breadth-First Search) 알고리즘을 사용합니다. BFS는 너비 우선 탐색 방식으로, 인접한 정점들을 우선적으로 탐색하는 알고리즘입니다.

코드 설명:

• 미로의 크기인 n과 m을 입력받습니다.
• 2차원 배열 maze를 생성하여 미로 정보를 저장합니다. 각 위치는 벽(0) 또는 통로(1)를 나타냅니다.
• 2차원 배열 dist를 생성하여 방문 여부와 최단 경로 길이를 저장합니다. 초기값으로 -1을 할당합니다.
• 시작 지점 (0, 0)을 큐에 넣고, dist[0][0]을 1로 설정하여 방문 처리합니다.
• 큐가 빌 때까지 다음 작업을 반복합니다:
  • 큐에서 원소를 하나 꺼내 현재 위치를 가져옵니다.
  • 현재 위치에서 상하좌우로 이동할 수 있는지 확인하고, 이동할 수 있는 경우:
    • 이동한 위치를 큐에 넣고, 현재 위치까지의 최단 경로 길이(dist[y][x])에 1을 더한 값을 할당합니다.
    • 이동한 위치를 방문 처리합니다.
• dist[n-1][m-1]에 저장된 값은 출발점에서 도착점까지의 최단 경로 길이입니다.

이 코드는 큐를 사용하여 BFS를 구현하고, 상하좌우로 인접한 위치를 탐색하면서 최단 경로를 찾아나갑니다. dist 배열은 방문 여부와 최단 경로 길이를 저장하기 위해 사용되며, 방문한 위치는 dist 배열의 해당 위치에 최단 경로 길이를 저장하고 방문 여부를 표시합니다.

BFS는 너비를 우선으로 탐색하기 때문에, 출발점에서 도착점으로의 경로 중 가장 짧은 경로를 찾아줍니다. 이를 통해 주어진 미로에서 출발점부터 도착점까지의 최단 경로 길이를 구할 수 있습니다.

자바스크립트

const readline = require("readline");
let n, m;
const maze = [];
let dist;
const input = [];

readline
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    const [nmLine, ...mazeLines] = input;
    [n, m] = nmLine.split(" ").map(Number);
    dist = new Array(n).fill(null).map(() => new Array(m).fill(-1));
    for (let i = 0; i < n; i++) {
      maze.push(mazeLines[i].split("").map(Number));
    }
    const result = solveMaze(n, m, maze, dist);
    console.log(result);
    process.exit();
  });

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

function solveMaze(n, m, maze, dist) {
  const queue = [];
  queue.push([0, 0]);
  dist[0][0] = 1;

  while (queue.length > 0) {
    const [y, x] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const ny = dy[i] + y;
      const nx = dx[i] + x;

      if (
        ny >= 0 &&
        ny < n &&
        nx >= 0 &&
        nx < m &&
        dist[ny][nx] === -1 &&
        maze[ny][nx] === 1
      ) {
        queue.push([ny, nx]);
        dist[ny][nx] = dist[y][x] + 1;
      }
    }
  }

  return dist[n - 1][m - 1];
}

파이썬

from collections import deque

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

def solveMaze(n, m, maze):
    dist = [[-1] * m for _ in range(n)]
    dist[0][0] = 1
    
    queue = deque()
    queue.append((0, 0))
    
    while queue:
        y, x = queue.popleft()
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny < n and 0 <= nx < m and maze[ny][nx] == 1 and dist[ny][nx] == -1:
                queue.append((ny, nx))
                dist[ny][nx] = dist[y][x] + 1
                
    return dist[n - 1][m - 1]

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

maze = []
for _ in range(n):
    line = list(map(int, input().strip()))
    maze.append(line)
    
result = solveMaze(n, m, maze)
print(result)