[소프티어] [HSAT 1회 정기 코딩 인증평가 기출] 로봇이 지나간 경로

27200 2025. 3. 31. 15:57
문제

풀이(25분)

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

public class Main {

    static int h, w;
    // 0 : 동, 1 : 남, 2 : 서, 3 : 북
    // 시계방향 회전(R)은 인덱스 -
    // 반시계방향 회전(L)은 인덱스 +
    static int[] dx = new int[]{0, 1, 0, -1}; // 동 남 서 북
    static int[] dy = new int[]{-1, 0, 1, 0}; // 동 남 서 북
    static final char[] direction = new char[]{'<', 'v', '>', '^'}; // 최종 출력을 위한 화살표
    static char[][] map; // 지도
    static ArrayList<Character> order = new ArrayList<>(); // 길 출력 순서
    static Point endPoint; // 도착점

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        map = new char[h][w];
        for(int i = 0; i < h; i++){ // 지도 입력
            String input = br.readLine();
            for(int j = 0; j < w; j++){
                map[i][j] = input.charAt(j);
            }
        }

        List<Point> startPoints = new ArrayList<>(); // 출발점으로 가능한 리스트

        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                int count = 0;
                int direction = 0;
                if(map[i][j] == '.'){
                    continue;
                }
                for(int k = 0; k < 4; k++){
                    int nextX = i + dx[k];
                    int nextY = j + dy[k];
                    if(nextX >= 0 && nextX < h && nextY >= 0 && nextY < w){ // 격자 안에 있으며
                        if(map[nextX][nextY] == '#'){ // 다음 이동 방향이 #이 됨
                            count++;
                            direction = k; // 첫번째 #이 이동 방향
                        }
                    }
                }
                if(count == 1){ // 만약 접한게 1개라면
                    startPoints.add(new Point(i, j, direction)); // 시작 리스트에 추가
                }
            }
        }

        endPoint = startPoints.get(1); // 첫 번째 포인트가 시작, 두 번째 포인트가 도착
        dfs(startPoints.get(0)); // 첫 번째 포인트를 기준으로 시작
        ArrayList<Character> firstList = new ArrayList<>(order);
        order.clear();
        endPoint = startPoints.get(0); // 두 번째 포인트가 시작, 첫 번째 포인트가 도착
        dfs(startPoints.get(1)); // 두 번째 포인트를 기준으로 시작
        ArrayList<Character> secondList = new ArrayList<>(order);
        StringBuilder sb = new StringBuilder();
        Point startPoint = null;
        if(firstList.size() > secondList.size()){ // 짧은 것을 찾기
            startPoint = startPoints.get(1);
            order = secondList;
        }else{
            startPoint = startPoints.get(0);
            order = firstList;
        }
        // 형식에 맞는 출력
        System.out.println((startPoint.x+1) + " " + (startPoint.y+1));
        System.out.println(direction[startPoint.direction]);
        for(int i = 0 ; i < order.size(); i++){
            sb.append(order.get(i));
        }
        System.out.println(sb);

    }

    // 방향을 어떤 쪽으로 바꾸는게 좋은지에 결정해주는 메서드
    static String directionChange(Point p){
        int leftTurn = 0; // 왼쪽으로 몇번 돌면 방향을 맞출 수 있는지
        int rightTurn = 0; // 오른쪽으로 몇번 돌면 방향을 맞출 수 있는지
        Point checkPoint = new Point(p.x, p.y, p.direction); // checkPoint를 복사해서 사용

        if(inside(checkPoint.x + dx[checkPoint.direction], checkPoint.y + dy[checkPoint.direction])){ // 회전할 필요가 없다면
            if(map[checkPoint.x + dx[checkPoint.direction]][checkPoint.y + dy[checkPoint.direction]] == '#'){
                return ""; // 공백을 리턴
            }
        }

        // 반시계 방향 체크
        for(int i = 0; i < 3; i++){ // 원래 방향을 바라볼 필요는 없으므로 최대 3번 반복
            leftTurn++;
            checkPoint.direction = (checkPoint.direction + 1) % 4; // 인덱스 맞춰주기
            if(inside(checkPoint.x + dx[checkPoint.direction], checkPoint.y + dy[checkPoint.direction])){
                if(map[checkPoint.x + dx[checkPoint.direction]][checkPoint.y + dy[checkPoint.direction]] == '#'){ // # 을 찾을 때까지 반복
                    break;
                }
            }
        }

        // 초기화 X -> 대신 방향을 원래 `p`에 적용하기 위해 저장해 둠
        int leftFinalDirection = checkPoint.direction;

        // 시계 방향 체크
        checkPoint.direction = p.direction; // 다시 원래 방향으로 복구
        for(int i = 0; i < 3; i++){
            rightTurn++;
            checkPoint.direction = (checkPoint.direction + 3) % 4; // 인덱스 맞춰주기
            if(inside(checkPoint.x + dx[checkPoint.direction], checkPoint.y + dy[checkPoint.direction])){
                if(map[checkPoint.x + dx[checkPoint.direction]][checkPoint.y + dy[checkPoint.direction]] == '#'){
                    break;
                }
            }
        }

        int rightFinalDirection = checkPoint.direction;

        // 방향 결정
        if(leftTurn > rightTurn){
            p.direction = rightFinalDirection; // 최종 방향을 원래 `p`에 적용
            return "R".repeat(rightTurn); // R을 몇번 사용했는지
        } else {
            p.direction = leftFinalDirection; // 최종 방향을 원래 `p`에 적용
            return "L".repeat(leftTurn); // L을 몇번 사용했는지
        }
    }


    // 경로는 백트래킹으로 만들 것임
    static void dfs(Point p){
        map[p.x][p.y] = '.'; // 최초 방문 체크
        if(p.x == endPoint.x && p.y == endPoint.y){
            map[p.x][p.y] = '#'; // 끝에 도달했다면 방문 체크 해제
            return;
        }
        String directionChange = directionChange(p); // 방향 맞춰주기
        for(char c : directionChange.toCharArray()){
            order.add(c); // 회전한만큼 List에 추가
        }
        order.add('A'); // 방향은 맞추어져 있으므로 A로 이동
        map[p.x + dx[p.direction]][p.y + dy[p.direction]] = '.'; // 한 칸 이동한 부분에 대해서만 방문 체크(도착한 칸은 dfs시작 시 체크 됨)
        dfs(new Point(p.x + 2 * dx[p.direction], p.y + 2 * dy[p.direction], p.direction)); // dfs
        map[p.x + dx[p.direction]][p.y + dy[p.direction]] = '#'; // 백트래킹
        map[p.x][p.y] = '#'; // 백트래킹
    }
    static boolean inside(int x, int y){
        if(x >= 0 && x < h && y >= 0 && y < w){
            return true;
        }
        return false;
    }



    static class Point {
        int x, y, direction;

        public Point(int x, int y, int direction) {
            this.x = x;
            this.y = y;
            this.direction = direction;
        }
    }
}
문제 풀이 전략

사실 어떻게 보면 단순한 dfs 문제이다. 다만, 정해진 이동 경로를 따라야 하기에 방향 전환을 어떻게 효율적으로 해주냐가 중요했다.
시작점과 끝점을 정한 뒤 2개의 경로를 갖게 된다.
방향 전환은 현재 방향을 기준으로 어떤 쪽으로 도는 게 효율적인지 판단한 후 추가한다.
또한, 방향 전환 메서드에 방향 전환 출력을 전적으로 일임하고 dfs메서드의 경우 정해진 방향으로 2칸 이동하는 것에만 초점을 두었다.