[구현] 백준 1347번 미로 만들기 - JAVA

 

 

미로를 따라 움직이는 것이 아닌

움직인 발자취를 보고 미로를 그려내는 문제

 

처음에는 어떻게 풀지?... 많은 고민을 했다가

아이디어를 생각해내고 '아!' 하게 했던 문제!

 

뿌듯해서 기록해본다.

야심한 새벽에 이 무슨 코딩 체조람

 

 

---

1. 출처

---

 

1347번: 미로 만들기

 

• 특정 크기의 지도에서 유저가 움직인 발자취가 주어진다. (직진, 왼쪽 회전, 오른쪽 회전)
• 발자취를 보고 지도를 다시 그려내는 문제
• #은 벽, . 은 이동 가능 위치
• 내가 어느 위치에서 시작하는지도 주어지지 않는다는 것이 포인트
• 방향은 어느 위치가 시작점이든 남쪽(아래)방향을 바라보고 있다.

 

 

---

2. 설계

---

 

 

1. 지도의 크기를 결정하는 방법

발자취를 보고 어떻게 지도의 크기를 정할까?

내가 택한 방법은 다음과 같다.

 

내가 어느 위치에서 시작하든 내 위치를 (0, 0)이라고 가정하는 것이다.

그 후 발자취대로 움직이며 위로 가면 row-1, 아래로 가면 row+1, 왼쪽으로 가면 col-1, 오른쪽으로 가면 col+1을 하면서

row의 최소, 최대 값과 col 최소, 최대 값을 구하면 된다.

 

예제 1번을 함께보며 시뮬레이션을 해보겠다.

5
RRFRF

 

 

 

현재 바라보는 방향 (row, col)	이동 명령	다음 방향 (row, col)
아래 (0, 0)	R	왼쪽 (0, 0)
왼쪽 (0, 0)	R	위 (0, 0)
위 (0, 0)	F	위 (-1, 0)
위 (-1, 0)	R	오른쪽 (-1, 0)
오른쪽 (-1, 0)	F	오른쪽 (-1, 1)

 

minR = -1 , maxR = 0

minC = 0 , maxC = 1

이라는 것을 알 수 있다.

 

위 결과로 row와 col의 크기를 알 수 있다.

• row 크기는 maxR - minR + 1 = 0 - (-1) + 1 = 2
• col 크기는 maxC - minC + 1 = 1 - 0 + 1 = 2

즉, 2X2 배열이였다는 것을 알 수 있다.

 

 

또한 유저의 시작점도 알 수 있다. 유저의 시작점은 (1, 0)이다.

• minR = -1 , maxR = 0 이라는 의미는 유저가 위로 1칸, 아래로 0칸 움직일 수 있다는 뜻이다.
• 즉, Math.abs(minR) 위치에 있다는 뜻이다.
• minC = 0 , maxC = 1 이라는 의미는 유저가 위로 0칸, 아래로 1칸 움직일 수 있다는 뜻이다.
• 즉, Math.abs(minC) 위치에 있다는 뜻이다.

 

 

2. 지도 구성하기

지도의 크기도 알았고, 유저의 시작 위치도 알았다.

그럼 다시 명령어를 읽어가면서 지도를 그리면 된다.

 

먼저 Arrays.fill을 이용해 지도 배열에 #로 초기화한다.

그리고 유저의 발자취대로 쭉 따라가다가 'F' 앞으로 가기 명령어가 나오면 # -> . 으로 변경해주면 된다.

 

지도 구성 후 출력해주면 끝이다.

 

 

---

3. 전체 코드

---

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

class Main {
    static int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};//상하좌우
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String info = br.readLine();

        //1. 지도 크기 구하기
        int curR = 0;
        int curC = 0;
        int minR = 0;
        int maxR = 0;
        int minC = 0;
        int maxC = 0;
        int direc = 1;//하
        for(int i=0; i<N; i++){
            char curPosition = info.charAt(i);
            if(curPosition=='F'){//전진
                curR = curR + drc[direc][0];
                curC = curC + drc[direc][1];
                minR = Math.min(minR, curR);
                maxR = Math.max(maxR, curR);
                minC = Math.min(minC, curC);
                maxC = Math.max(maxC, curC);
            }else{//방향전환
                direc = ChangeDirec(curPosition, direc);
            }
        } //end for
        

        //2. 점찍기
        int row = maxR - minR + 1;
        int col = maxC - minC + 1;
        int startR = Math.abs(minR);
        int startC = Math.abs(minC);

        char[][] map = new char[row][col];
        for(int i=0; i<row; i++){
            Arrays.fill(map[i], '#');
        }        
        map[startR][startC] = '.';

        direc = 1;//하
        for(int i=0; i<N; i++){
            char curPosition = info.charAt(i);
            if(curPosition=='F'){//전진
                startR = startR + drc[direc][0];
                startC = startC + drc[direc][1];
                map[startR][startC] = '.';
            }else{//방향전환
                direc = ChangeDirec(curPosition, direc);
            }
        }

        //3. 출력
        StringBuilder sb = new StringBuilder();
        for(int r=0; r<row; r++){
            for(int c=0; c<col; c++){
                sb.append(map[r][c]);
            }
            sb.append("\n");
        }

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

    public static int ChangeDirec(char curPosition, int direc){
        if(curPosition=='L'){
            if(direc == 0) direc = 2; //상 -> 좌
            else if(direc == 1) direc = 3; //하 -> 우
            else if(direc == 2) direc = 1; //좌 -> 하
            else direc = 0; //우 -> 상
        }else{//'R'
            if(direc == 0) direc = 3; //상 -> 우
            else if(direc == 1) direc = 2; //하 -> 좌
            else if(direc == 2) direc = 0; //좌 -> 상
            else direc = 1; //우 -> 하
        }

        return direc;
    }
}

//row : 3
//col : -3

//min row : 0
//max row : 6

//min col : -6
//max col : 0

//입력 받으면서 위 과정 진행
//row, col구하면 map 생성
//#으로 fill
//방향 이동하면서 F위치로 이동하며 . 업데이트