[백준 알고리즘] 1347번 미로 만들기(Java) 문제 풀이

2 초

128 MB

2911

1534

1308

53.983%

문제

홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍준이는 미로에서 모든 행과 열의 이동할 수 있는 칸을 걸어다녔다. 그러면서 자신의 움직임을 모두 노트에 쓰기로 했다. 홍준이는 미로의 지도를 자기 노트만을 이용해서 그리려고 한다.

입력으로 홍준이가 적은 내용을 나타내는 문자열이 주어진다. 각 문자 하나는 한 번의 움직임을 말한다. ‘F’는 앞으로 한 칸 움직인 것이고, ‘L'과 ’R'은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 즉, 90도를 회전하면서, 위치는 그대로인 것이다.

입력

첫째 줄에 홍준이가 적은 내용의 길이가 주어진다. 길이는 0보다 크고, 50보다 작다. 둘째 줄에 홍준이가 적은 내용이 내용이 주어진다.

출력

첫째 줄에 미로 지도를 출력한다. ‘.’은 이동할 수 있는 칸이고, ‘#’는 벽이다.

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

1347번: 미로 만들기

문제에 대한 이해

주어진 문자열 명령어를 이용하여, 미로를 그리는 단순 구현 문제였다.

어떻게 풀 것인가?

이 문제를 처음 딱 보았을 때, 2차원 배열의 크기를 어떻게 할당할 것일까에 대하여 오랫동안 고민하였다. 하지만, 문제를 꼼꼼하게 읽지 않고 문제를 풀려고하는 습관때문에 오래걸렸다. 주어진 문자열에는 50까지의 길이가 주어진다. 이 말은 2차원 배열의 가장 큰 크기는 50이다. 그렇다면 50의 2배인 100 X 100 2차원 배열을 처음에 할당하고 처음 시작 지점을 한가운데에 놓으면 어떠한 방향으로 F하여 이동한다 할지라도 벗어나지 않는다.

하지만 문제를 볼 때는 생각이 나지않아서, 결국에는 풀이를 참고하였다.

참고 블로그

https://kwangkyun-world.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-1347-%EB%AF%B8%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0

[Java/자바 백준 1347] 미로 만들기

시간복잡도

시간복잡도는 크게 고려하지 않았으나, O(N)이라고 생각한다.

공간복잡도

2차원 배열의 크기를 고려한다면 O(N^2)라고 생각한다.

풀면서 놓쳤던점

구현 문제에 대하여 많이 약하다는 것을 느꼈다.

이 문제를 통해 얻어갈 것

구현 문제를 조금 더 많이 연습을 해야할 것 같다.

내 코드 

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

// 백준알고리즘 1347번 미로 만들기

public class Main {
    static int N;
    static String str;

    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));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());
        str = br.readLine();
        int[][] map = new int[101][101];
        int x = 50;
        int y = 50;
        int maxX = 50;
        int maxY = 50;
        int minX = 50;
        int minY = 50;
        map[x][y] = 1;

        int dir = 2;
        for (int i = 0; i < N; i++) {
            if (str.charAt(i) == 'L') {
                dir -= 1;
                if (dir == -1) dir = 3;
            } else if (str.charAt(i) == 'R') {
                dir = (dir + 1) % 4;
            } else if (str.charAt(i) == 'F') {
                x = x + dx[dir];
                y = y + dy[dir];
                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);
                map[x][y] = 1;
            }

        }
        for (int i = minX; i <= maxX; i++) {
            for (int j = minY; j <= maxY; j++) {
                if (map[i][j] == 1) {
                    sb.append(".");
                } else {
                    sb.append("#");
                }
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}