[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

https://softeer.ai/practice/6275

 

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

 

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

[소프티어] 6275번 - 로봇이 지나간 경로 [Java]

---

1.  아이디어

 

방문한 곳을 다시 방문하지 않으면서 좌우 회전과 바라보는 방향으로 두 칸 이동하는 로봇의 움직임은 폐곡선을 만들지 않으면서 한붓그리기가 가능한 경로로 움직이게 된다. 따라서 방문한 칸이면서 사방에 방문한 칸이 한칸 밖에 없는 지점 두 개가 가능한 출발지가 된다. 해당 출발지에서 DFS 알고리즘을 통해 위치와 방향을 들고 다니며 명령을 구하는 방식으로 구현했다.

---

2. 문제풀이

 

입력을 받은 후 시작 위치와 방향을 먼저 찾았다. 맵을 순회하며 방문한 칸일 때 사방에 방문한 칸이 하나밖에 없는 곳이면 시작 위치와 방향을 구한 후 종료했고 이후 해당 정보로 DFS 탐색을 시작했다. DFS는 방문 후 다음 위치를 찾을 때 다음 위치와 현재 바라보는 방향이 동일하면 그냥 이동하고 다르면 회전 후 이동을 해야하는데 이때 사방탐색 배열을 시계방향 또는 반시계방향으로 일관되게 설정했으면 오른쪽 회전은 사방탐색 배열에서 인덱스의 증가, 왼쪽 회전은 사방탐색 배열에서 인덱스의 감소로 구할 수 있다. 이때 인덱스의 범위를 벗어나는 문제를 해결하기 위해 배열의 크기인 4만큼 더하고 다시 모듈러 연산을 해주면 된다. 사방탐색 배열은 인접한 칸인 1칸을 기준으로 설정하지만 로봇의 이동은 2칸씩 이루어짐에 주의해야하고 사방탐색 배열을 2칸으로 설정하면 잘못된 경로로 이동할 수 있음에 주의해야한다.

---

3. 코드

 

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

public class Main {

    private static final StringBuilder sb = new StringBuilder();

    // 상 우 하 좌 사방탐색 배열
    private static final int[] dr = {-1, 0, 1, 0};
    private static final int[] dc = {0, 1, 0, -1};

    private static int H;
    private static int W;
    private static char[][] map;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        int r = -1;  // 로봇의 시작 행
        int c = -1;  // 로봇의 시작 열
        int d = -1;  // 로봇의 시작 방향

        map = new char[H][W];
        for (int i = 0; i < H; i++) {
            map[i] = br.readLine().toCharArray();
        }

        // 로봇의 시작 위치와 방향 찾기
        out:
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (map[i][j] == '.') continue;

                int cntVisited = 0;  // 인접한 칸 중 방문한 칸의 개수
                int dirVisited = -1;  // 인접한 칸 중 방문한 칸의 방향

                for (int dir = 0; dir < 4; dir++) {
                    int nr = i + dr[dir];
                    int nc = j + dc[dir];

                    if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
                    if (map[nr][nc] == '#') {
                        cntVisited++;
                        dirVisited = dir;
                    }
                }

                // 인접한 칸 중 방문한 칸이 정확히 1개면 시작 위치 후보
                if (cntVisited == 1) {
                    r = i;
                    c = j;
                    d = dirVisited;
                    break out;
                }
            }
        }

        visited = new boolean[H][W];

        sb.append(r + 1).append(" ").append(c + 1).append("\n");
        if (d == 0) sb.append("^").append("\n");
        else if (d == 1) sb.append(">").append("\n");
        else if (d == 2) sb.append("v").append("\n");
        else if (d == 3) sb.append("<").append("\n");

        dfs(r, c, d);

        bw.write(sb.toString());
        bw.flush();
    }

    private static void dfs(int r, int c, int d) {
        visited[r][c] = true;

        for (int dir = 0; dir < 4; dir++) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            if (map[nr][nc] == '.' || visited[nr][nc]) continue;

            // 바라보는 방향으로 이동하는 경우
            if (d == dir) {
                sb.append("A");
                dfs(nr + dr[dir], nc + dc[dir], dir);
            }
            // 오른쪽으로 회전 후 이동하는 경우
            else if ((d + 1) % 4 == dir) {
                sb.append("RA");
                dfs(nr + dr[dir], nc + dc[dir], dir);
            }
            // 왼쪽으로 회전 후 이동하는 경우
            else if ((d - 1 + 4) % 4 == dir) {
                sb.append("LA");
                dfs(nr + dr[dir], nc + dc[dir], dir);
            }
        }
    }

}

---

4. 후기