[JAVA] 백준 1347 : 미로만들기

문제

홍준이는 미로의 남쪽을 보면서 서 있으며 명령에 따라 움직인다. F가 나오면 해당 방향으로 이동하고, R이나 L이 나오면 현재 방향을 기준으로 왼쪽이나 오른쪽으로 방향을 바꾼다. 명령에 따라 움직인 것은 미로에서 갈 수 있는 모든 곳이라고 했을 때, 갈 수 있는 길은 '.'로, 갈 수 없는 길은 '#'로 미로를 출력한다.

접근방법

1. 처음 좌표를 (0,0)으로 두고, 이동한 좌표를 저장한다.

   • 현재 방향을 direct로 두고, 방향 명령어(R, L)이 나오면 이 방향을 바꿔준다.

   • 이동 명령어(F)가 들어오면 현재 위치를 기준으로 해당 방향으로 이동한 좌표를 리스트에 저장한다.

     ex) 현재 좌표 (0, 1)이며 현재 방향이 위쪽일 때 이동명령어(F)가 들어오면 (-1, 1) 좌표를 만들어 저장한다.

2. x, y 각각의 max, min 값을 저장 한 뒤, 이 값을 이용해 배열의 크기를 정한다.

   • (0, 0), (-1, 0), (-1, 1) 로 이동했다고 할 때, 만들어지는 배열의 크기는 (max_x - min_x + 1) * (max_y - min_y + 1)이 된다.

   • 주어진 조건에서 '모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다'고 했으므로, 이동한 칸을 중심으로 배열을 만들고 그 중에서 이동하지 않은 칸은 벽('#')으로 채워주면 된다.

   • int[][] map = new int[max_x - min_x + 1][max_y - min_y + 1];

3. 이동한 좌표의 가장 왼쪽 위의 값을 (0, 0)으로 바꾸어 배열에 넣는다.

   • 처음 (0, 0) 을 기준으로 상대좌표를 저장하고 있기 때문에, 모든 좌표에서 min_x를 0으로, min_y를 0으로 만들면 가장 작은 값이 왼쪽 위가 되므로 절대 좌표로 바꾸어준다.

     for(int i=0; i<poses.size(); i++){
         int x = poses.get(i).x + (-1 * min_x);
         int y = poses.get(i).y + (-1 * min_y);
         map[x][y] = 1;
     }

4. 이동한 좌표를 배열에 표시한 다음, 주어진 출력 형식에 맞춰 출력한다.

소스코드

static class Pos{
    int x; int y;
    public Pos(int x, int y) {this.x = x; this.y = y;}
}
​
static Pos cur_pos;
static int direct; // 방향 : 위(0), 오른(1), 아래(2), 왼(3)
​
// 방향 회전
static void rotate(char dir){
    if(dir == 'R'){
        ++direct;
        if(direct > 3)
            direct = 0;
    }else if(dir == 'L'){
        --direct;
        if(direct < 0)
            direct = 3;
    }
}
​
public static void main(String[] args) throws IOException{
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(in.readLine());
    String command = in.readLine();
​
    cur_pos = new Pos(0,0); // 처음 좌표 : (0, 0)
    direct = 2; // 처음 방향 : 남쪽
​
    ArrayList<Pos> poses = new ArrayList<>();
    poses.add(new Pos(0,0));
​
    int min_x, min_y, max_x, max_y;
    min_x = min_y = max_x = max_y = 0;
​
    for(int i=0; i<N; i++){
        // 해당 방향으로 이동
        if(command.charAt(i) == 'F'){
            if(direct == 0)
                --cur_pos.x;
            else if(direct == 1)
                ++cur_pos.y;
            else if(direct == 2)
                ++cur_pos.x;
            else if(direct == 3)
                --cur_pos.y;
​
            poses.add(new Pos(cur_pos.x, cur_pos.y));
​
            // 최대값-최솟값 저장
            if(cur_pos.x > max_x) max_x = cur_pos.x;
            else if(cur_pos.x < min_x) min_x = cur_pos.x;
            if(cur_pos.y > max_y) max_y = cur_pos.y;
            else if(cur_pos.y < min_y) min_y = cur_pos.y;
​
        }
        else{ // 방향 전환
            rotate(command.charAt(i));
        }
​
    }
​
    int[][] map = new int[max_x - min_x + 1][max_y - min_y + 1];
​
    // 가장 왼쪽 위 좌표 (0,0)으로 만들기
    for(int i=0; i<poses.size(); i++){
        int x = poses.get(i).x + (-1 * min_x);
        int y = poses.get(i).y + (-1 * min_y);
        map[x][y] = 1;
    }
​
​
    // answer
    for(int i=0; i<map.length; i++){
        for(int j=0; j<map[0].length; j++){
            if(map[i][j] == 1)
                System.out.print('.');
            else
                System.out.print("#");
        }
        System.out.println();
    }
}