[알고리즘 TIL] Q1347(구현)

문제

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

트러블슈팅

1. 90도 회전 공식

미로 안에서 "R"(오른쪽) 또는 "L"(왼쪽) 명령에 따라 캐릭터의 이동 방향을 회전시켜야 했다. 나는 현재 방향을 (dy, dx) 형태의 2차원 벡터로 관리하고 있었고, 처음에는 동서남북 각각의 방향마다 +1, -1 연산이 다 달라서, "회전은 규칙 없이 분기문으로만 처리해야 하나?" 라는 고민을 했다.

 

하지만 알고 보니, 2차원 벡터를 기준으로 명확한 회전 공식이 존재했다.

//시계 방향 90도 회전
(dy, dx) → (dx, -dy)
//반시계 방향 90도 회전
(dy, dx) → (-dx, dy)

이 공식을 적용하면, 각 방향을 기준으로 분기 처리할 필요 없이 간단하게 한 줄로 방향 회전이 가능해졌다.

 

2. 배열 생성 인덱스 갯수

방문 좌표 리스트를 기반으로 미로를 출력할 때, maxY, minY, maxX, minX를 계산하여 배열의 행과 열 길이를 다음과 같이 만들었었다.

int rowLength = maxY - minY;
int colLength = maxX - minX;​

그런데 여기서 +1이 누락된 것이 핵심 오류였다. 예를 들어 minX = 0, maxX = 4일 경우, 0~4까지 총 5칸이 필요한데 4칸짜리 배열만 만들어진 것이다. 결과적으로, 방문한 좌표 중 하나가 배열 범위를 초과해 예외가 발생했다.

 

따라서, 다음과 같이 수정했다.

int rowLength = maxY - minY + 1;
int colLength = maxX - minX + 1;

좌표 기반 범위를 배열로 표현할 때는, "최댓값 - 최솟값 + 1"이 필요하다는 점을 새로 알았다.

구현

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

public class Q1347 {

    static int dy = 1;
    static int dx = 0;
    static int maxX = Integer.MIN_VALUE;
    static int maxY = Integer.MIN_VALUE;
    static int minX = Integer.MAX_VALUE;
    static int minY = Integer.MAX_VALUE;

    static ArrayList<int[]> visited = new ArrayList<>();

    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 nowY = 0;
        int nowX = 0;

        visited.add(new int[]{nowY, nowX});
        visited.add(new int[]{nowY, nowX});

        int n = Integer.parseInt(br.readLine());
        String[] inputStr = br.readLine().split("");
        for (int i = 0; i < n; i++) {
            String move = inputStr[i];
            int temp = dy;
            switch (move) {
                case "R":
                    dy = dx;
                    dx = -temp;
                    break;
                case "L":
                    dy = -dx;
                    dx = temp;
                    break;
                case "F":
                    nowY += dy;
                    nowX += dx;
                    visited.add(new int[]{nowY, nowX});
                    visited.add(new int[]{nowY, nowX});
            }
        }
        boolean[][] miro = generateMiro();
        printMiro(miro, bw);

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

    private static boolean[][] generateMiro() {
        for (int i = 0; i < visited.size(); i++) {
            int[] visitedPos = visited.get(i);
            int visitedPosX = visitedPos[1];
            int visitedPosY = visitedPos[0];
            if (maxX < visitedPosX) maxX = visitedPosX;
            if (maxY < visitedPosY) maxY = visitedPosY;
            if (minX > visitedPosX) minX = visitedPosX;
            if (minY > visitedPosY) minY = visitedPosY;
        }

        int rowLength = Math.abs(maxY - minY) + 1;
        int colLength = Math.abs(maxX - minX) + 1;
        boolean[][] miro = new boolean[rowLength][colLength];
        int plusX = -minX;
        int plusY = -minY;

        for (int i = 0; i < visited.size(); i++) {
            int[] visitedPos = visited.get(i);
            int visitedPosX = visitedPos[1];
            int visitedPosY = visitedPos[0];
            miro[visitedPosY + plusY][visitedPosX + plusX] = true;
        }
        return miro;
    }

    private static void printMiro(boolean[][] miro, BufferedWriter bw) throws IOException {
        for (int i = 0; i < miro.length; i++) {
            boolean[] miroAtI = miro[i];
            for (int j = 0; j < miro[0].length; j++) {
                boolean isCanGo = miroAtI[j];
                if (isCanGo) bw.write(".");
                else bw.write("#");
            }
            bw.write("\n");
        }
    }
}