[BOJ] 백준 1347 - 미로 만들기 풀이

1. 문제

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

1347번: 미로 만들기

 

2. 풀이

백준의 구현 카테고리의 문제이다.

문제를 보고 '현재 위치도 주어지지 않고 방문한 곳을 체크를 어떻게 할 수 있을까'에 대한 고민을 20분 했다. 이에 대한 힌트는 '길이는 0보다 크고, 50보다 작다.' 라는 문구에서 얻을 수 있었다.

길이가 0~49까지 주어질 때, F만 주어진다면 갈 수 있는 길이는 최대 50이다. 그리고 동서남북 다 갈 수 있으므로 위, 아래, 왼쪽, 오른쪽으로 50씩 갈 수 있는 것이다. 따라서 배열을 100X100으로 만들면 최대 배열의 크기가 된다.

최대 배열로 잡았으므로 임의의 위치를 잡는다. 이때 F가 50번 나올 수도 있으므로 임의의 점은 (50, 50)으로 잡는다.
그 후 방위를 계산하여 방문한 곳을 체크한 후 움직인 공간이 전부 포함된 부분 배열을 출력하면 된다.

부분 배열을 출력할 때는 직사각형의 특성을 생각하면 된다.
직사각형은 왼쪽 위의 꼭짓점의 좌표와 오른쪽 아래의 꼭짓점의 좌표를 알면 넓이, 길이 등을 구할 수 있다.
따라서 최대 길이 반복문을 돌면서 '.'이 처음 나오는 좌표를 저장해두고, '.'이 나올 때마다 왼쪽 위의 꼭짓점은 최소값을, 오른쪽 아래의 꼭짓점은 최대 값을 갱신해주면 양끝의 점의 좌표를 구할 수 있다.

마지막으로, 구한 좌표의 길이에 따라 반복문을 돌리면 정답!!!

3. 소스 코드

import java.io.*;

public class Main {
    static char[][] map;
    static int dir = 1;  // 0 : 동, 1 : 남, 2: 서, 3 : 북

    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int cnt = Integer.parseInt(br.readLine());
        String input = br.readLine();

        map = new char[101][101];
        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < 101; j++) {
                map[i][j] = '#';
            }
        }

        int nowX = 50;
        int nowY = 50;
        map[nowX][nowY] = '.';

        for (int i = 0; i < cnt; i++) {
            char c = input.charAt(i);

            switch (c) {
                case 'F':
                    map[nowX + dy[dir]][nowY + dx[dir]] = '.';

                    nowX += dy[dir];
                    nowY += dx[dir];
                    break;

                case 'L':
                    setDirMethod(c);
                    break;

                case 'R':
                    setDirMethod(c);
                    break;
            }
        }

        int StartX = 0;
        int StartY = 0;

        int EndX = 0;
        int EndY = 0;

        int pointCnt = 0;

        for (int i = 0; i < 101; i++) {
            for (int j = 0; j < 101; j++) {
                if (map[i][j] == '.') {
                    if (pointCnt == 0) {
                        StartX = i;
                        StartY = j;

                        EndX = i;
                        EndY = j;
                        pointCnt += 1;
                    }

                    else {
                        StartX = Math.min(StartX, i);
                        StartY = Math.min(StartY, j);

                        EndX = Math.max(EndX, i);
                        EndY = Math.max(EndY, j);
                    }
                }
            }
        }

        for (int i = StartX; i <= EndX; i++) {
            for (int j = StartY; j <= EndY; j++) {
                bw.write(map[i][j]);
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    static void setDirMethod(char c) {
        if (c == 'R') {
            if (dir == 0) {
                dir = 3;
            } else {
                dir -= 1;
            }
        } else if (c == 'L') {
            if (dir == 3) {
                dir = 0;
            } else {
                dir += 1;
            }
        }
    }
}