[파이썬, 자바] 백준 24463 : 미로 (골드4)

[파이썬, 자바] 백준 24463 : 미로 (골드4)

• https://www.acmicpc.net/problem/24464

---

풀이

방향성 생각

• BFS + 역추적 사용하기.
• DFS를 하기에는 너무 맵 사이즈가 커서 TLE 우려가 있어서 BFS 사용
• 풀이
  1. 테두리에서 start, end 탐색
  2. BFS + 역추적 기록
  3. 역추적 복원 후 2D 배열 순회하면서 복원 set에 있는지 확인
  4. 출력

 

---

파이썬

from collections import deque
import sys

input = lambda : sys.stdin.readline().rstrip()
inside = lambda x,y : 0<=x<W and 0<=y<H
dires = [(1,0),(0,1),(-1,0),(0,-1)]

H,W = map(int,input().split())
arr = [list(input()) for _ in range(H)]

locs = []
for j in [0,W-1]:
    for i in range(H-1):
        if arr[i][j] == '.':
            locs.append((j,i))
for i in [0,H-1]:
    for j in range(W-1):
        if arr[i][j] == '.':
            locs.append((j,i))
sx,sy = locs[0]
ex,ey = locs[1]

Q = deque([(sx,sy)])
V = [[False]*W for _ in range(H)]
V[sy][sx] = True
trace = [[(-1,-1)]*W for _ in range(H)]

while Q:
    cx,cy = Q.popleft()

    for dx,dy in dires:
        nx,ny = cx+dx, cy+dy
        if inside(nx,ny) and arr[ny][nx] == '.' and not V[ny][nx]:
            Q.append((nx,ny))
            V[ny][nx] = True
            trace[ny][nx] = (cx,cy)

paths = [(ex,ey)]
while paths[-1] != (-1,-1):
    cx,cy = paths[-1]
    paths.append(trace[cy][cx])

paths = set(paths)
for i in range(H):
    for j in range(W):
        if arr[i][j] == '.' and (j,i) not in paths:
            arr[i][j] = '@'

for row in arr:
    print(''.join(row))

자바

import java.io.*;
import java.util.*;

public class Main {

    public static int H;
    public static int W;
    public static char[][] arr;
    public static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        arr = new char[H][W];

        for (int i = 0; i < H; i++) {
            String line = br.readLine();
            arr[i] = line.toCharArray();
        }

        List<int[]> locs = new ArrayList<>();
        int[] sideCols = {0, W - 1};
        int[] sideRows = {0, H - 1};

        for (int j : sideCols) {
            for (int i = 0; i < H; i++) {
                if (arr[i][j] == '.') locs.add(new int[] {j, i});
            }
        }

        for (int i : sideRows) {
            for (int j = 0; j < W; j++) {
                if (arr[i][j] == '.') locs.add(new int[] {j, i});
            }
        }

        int[] startLoc = locs.get(0);
        int sx = startLoc[0], sy = startLoc[1];
        int[] endLoc = locs.get(1);
        int ex = endLoc[0], ey = endLoc[1];

        ArrayDeque<int[]> Q = new ArrayDeque<>();
        boolean[][] V = new boolean[H][W];
        V[sy][sx] = true;

        int[][] trace = new int[H][W];
        for (int i = 0; i < H; i++) {
            Arrays.fill(trace[i], -1);
        }

        Q.offer(new int[] {sx, sy});

        while (!Q.isEmpty()) {
            int[] cinfo = Q.poll();
            int cx = cinfo[0], cy = cinfo[1];

            for (int[] dire : dires) {
                int nx = cx + dire[0], ny = cy + dire[1];

                if (nx >= 0 && nx < W && ny >= 0 && ny < H && arr[ny][nx] == '.' && !V[ny][nx]) {
                    V[ny][nx] = true;
                    Q.offer(new int[] {nx, ny});
                    trace[ny][nx] = cy*W + cx; 
                }
            }
        }

        List<Integer> paths = new ArrayList<>();
        paths.add(ey * W + ex);

        while (trace[paths.get(paths.size() - 1) / W][paths.get(paths.size() - 1) % W] != -1) {
            int cur = paths.get(paths.size() - 1);
            int cx = cur % W, cy = cur / W;
            int prev = trace[cy][cx];
            paths.add(prev);
        }

        Set<Integer> pathSet = new HashSet<>(paths);

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (arr[i][j] == '.') {
                    sb.append(pathSet.contains(i * W + j) ? '.' : '@');
                } else {
                    sb.append(arr[i][j]); 
                }
            }
            sb.append("\n");
        }

        System.out.print(sb.toString());
        }
}

---

코멘트

• 파이썬이 자료형이 편해서 대충대충 짜느라 2D 배열 좌표를 1차원으로 반환하는 방식은 잘 안썼는데, 굳이 사이즈 크게 튜플로 할당하거나 ArrayList 쓰는 방식보다는 간단하게 i*W+j로 반환하는게 더 나은 듯 하다.