[백준/BOJ] 1347번 - 미로 만들기 (Python, Java)

· 문제링크

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

1347번: 미로 만들기

· 핵심

1. 시작점이 설정되어있지 않다.

→ 명령어의 최대 길이는 50이므로 넉넉하게 아주 큰 board를 생성하고 적절한 시작점을 임의로 설정한다.

→ max_n = 200, cr = max_n // 2 , cc = max_n // 2

2. 큰 board에서 이동한 영역을 추출하기

→ 도착을 1로 표시

→ 사각형을 추출하기 위해서 1이 존재하는 (행, 열)들 중에서 min_r,  min_c, max_r,  max_c 를 얻으면 사각형의 왼쪽상단과 오른쪽하단 좌표를 얻는 것과 동일하다.

 

for r in range(max_n):
    for c in range(max_n):
        if result_board[r][c] == 1:
            max_r = max(max_r, r)
            min_r = min(min_r, r)
            max_c = max(max_c, c)
            min_c = min(min_c, c)

---

· 코드(Python)

max_n = 200

n = int(input())
cmds = input()
# 격자 내 이동 - 동남서북
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def simulate(cr, cc, cmds):
    # 현재 방향
    board = [[0 for _ in range(max_n)] for _ in range(max_n)]
    dir = 1
    board[cr][cc] = 1
    for cmd in cmds:
        if cmd == 'R':
            dir = (dir + 1) % 4
        elif cmd == 'L':
            dir = (dir + 3) % 4
        else:
            nr = cr + dr[dir]
            nc = cc + dc[dir]
            cr, cc = nr, nc
            board[cr][cc] = 1
    return board


result_board = simulate(max_n // 2, max_n // 2, cmds)

max_r, min_r, max_c, min_c = 0, max_n, 0, max_n

for r in range(max_n):
    for c in range(max_n):
        if result_board[r][c] == 1:
            max_r = max(max_r, r)
            min_r = min(min_r, r)
            max_c = max(max_c, c)
            min_c = min(min_c, c)

# print(max_r, max_c, min_r, min_c)
for r in range(min_r, max_r + 1):
    for c in range(min_c, max_c + 1):
        if result_board[r][c] == 0:
            print('#', end = '')
        else:
            print('.', end = '')
    print()

---

· 코드(Java)

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 200;
    public static final int[] dr = {0, 1, 0, -1}; // 동남서북
    public static final int[] dc = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String cmds = sc.next();

        int[][] board = new int[MAX_N][MAX_N];
        int cr = MAX_N / 2, cc = MAX_N / 2;
        int dir = 1; // 초기 방향은 남쪽

        board[cr][cc] = 1;
        for (char cmd: cmds.toCharArray()) {
            if (cmd == 'R') {
                dir = (dir + 1) % 4;
            } else if (cmd == 'L') {
                dir = (dir + 3) % 4;
            } else {
                int nr = cr + dr[dir], nc = cc + dc[dir];
                cr = nr; cc = nc;
                board[cr][cc] = 1;
            }
        }

        int maxR = 0, minR = MAX_N, maxC = 0, minC = MAX_N;
        for (int r = 0; r < MAX_N; r++) {
            for (int c = 0; c < MAX_N; c++) {
                if (board[r][c] == 1) {
                    maxR = Math.max(maxR, r);
                    minR = Math.min(minR, r);
                    maxC = Math.max(maxC, c);
                    minC = Math.min(minC, c);
                }
            }
        }

        for (int r = minR; r <= maxR; r++) {
            for (int c = minC; c <= maxC; c++) {
                if (board[r][c] == 0) {
                    System.out.print("#");
                } else {
                    System.out.print(".");
                }
            }
            System.out.println();
        }
    }
}