[백준] 1347. 미로 만들기 - 실버4

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

1347번: 미로 만들기

 

문제 요약

입력으로 움직임이 주어진다. 움직임은 총 세 개로, F는 앞으로 한 칸, L과 R은 방향을 왼쪽 또는 오른쪽으로 전환한 것이다. 첫 시작은 남쪽을 보며 서 있다. 입력이 주어졌을 때 해당되는 미로 지도를 출력하시오. 이동할 수 있는 칸은 '.', 벽은 '#'이다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다.

 

문제 해결 아이디어

어려운 문제였다... 미리 미로의 크기를 알 수 없으므로 문제에서 입력이 50보다 작다고 했으므로 49, 49에서 시작한다고 가정하여 미로를 채우기로 했다. 출력을 위해 움직임에 따라 미로의 시작과 끝을 변수에 저장해야 했다.

현재 방향을 저장해 두는 변수 dir을 사용했고, 방향에 따라 숫자가 바뀐다. 그 숫자는 방향을 저장해 둔 배열의 인덱스가 될 것이다. L R이 입력될 때마다 인덱스를 넘어가면 관리해 주었다.

현재 위치를 x, y로 표현했다.

'F'가 입력된 경우에는 현재 위치에 현재 방향을 고려해 갱신했고, 해당 위치의 배열값을 '.'로 갱신했다. 그 위치는 갈 수 있다는 뜻이기 때문이다.

제일 관건은 그 이후인데, 처음에는 그냥 미로의 시작과 끝을 더하고 빼주는 식으로 했다. 그렇지만 계속해서 새로운 길을 개척해 나가는 것이 아니라 같은 자리를 빙빙 돌 수도 있으므로 미로의 시작과 끝, 갱신된 위치의 값을 비교해 주어야 했다.

 

완성된 코드

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

public class Main_BOJ_1347_미로만들기 {
	/*
	 * 76ms
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		char[] input = new char[N];

		String s = br.readLine();
		for (int i = 0; i < N; i++) {
			input[i] = s.charAt(i);
		}

		// 미리 미로의 크기를 알 수 없으니 미로 크기의 변수값을 가지고 다녀야 한다
		// 50번이 이동의 최대이므로 49, 49에서 시작해서 미로 채우기
		char[][] maze = new char[102][102];
		for (int i = 0; i < 102; i++) {
			Arrays.fill(maze[i], '#');
		}

		// 하 좌 상 우
		int[] dr = { 1, 0, -1, 0 };
		int[] dc = { 0, -1, 0, 1 };

		// 시작
		maze[49][49] = '.';
		int x = 49, y = 49;
		int min_r = 49, min_c = 49, max_r = 49, max_c = 49;
		int dir = 0;
		for (int i = 0; i < N; i++) {
			if (input[i] == 'F') {
				x += dr[dir];
				y += dc[dir];

				maze[x][y] = '.';
				min_r = Math.min(min_r, x);
				max_r = Math.max(max_r, x);
				min_c = Math.min(min_c, y);
				max_c = Math.max(max_c, y);
			} else if (input[i] == 'R') {
				dir = dir == 3 ? 0 : dir + 1;
			} else { // L
				dir = dir == 0 ? 3 : dir - 1;
			}
		}

		for (int i = min_r; i <= max_r; i++) {
			for (int j = min_c; j <= max_c; j++) {
				sb.append(maze[i][j]);
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
}