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

https://softeer.ai/practice/6275/history?questionType=ALGORITHM

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

풀이과정

전체적인 풀이

1. 탐색 경로의 시작점, 시작 방향 찾기

2. 찾은 방향으로 dfs탐색하기

2-1. 현재 방향으로 두 칸 이동할 수 있는지 확인

2-2. 오른쪽으로 회전 시킨 뒤, 두 칸 이동할 수 있는지 확인

2-3. 왼쪽으로 회전 시킨 뒤, 두 칸 이동할 수 있는지 확인

 

 

자세한 풀이

시작점이 될 수 있는 좌표

1. "#" 인 문자열

2. 상, 하, 좌, 우 "#" 문자열이 하나 있어야 함 (두 개 이면 안됨)

 

위 두 가지 특징을 활용해서 모든 좌표에 대해 탐색하며 시작점을 찾았습니다.

static void find_start(){
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(map[i][j].equals("#")){
                    int cnt = 0;
                    for(int d=0;d<4;d++){
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if(is_range(nr,nc) && map[nr][nc].equals("#")){
                            cnt+=1;
                            sd = d;
                            if(cnt>1) break;
                        }
                    }
                    if(cnt==1){
                        sr = i;
                        sc = j;
                        return;
                    }
                }
            }
        }
        
    }

이때 시작점을 찾게 되면, 더 이상 다른 시작점을 찾지 않아도 되므로 바로 함수를 종료했습니다.

 

dfs을 통해서 command 찾기

dfs함수의 매개변수로 좌표(r, c)와 방향(d)를 넘겨줬습니다.

 

1. 현재 방향으로 두 칸 이동할 수 있으면 두 칸 이동한 (nr, nc)와 원래 방향(d)으로 dfs를 수행합니다.

 

2. 현재 방향으로 이동할 수 없으면 오른쪽으로 회전 시키고, 두 칸 이동할 수 있는지 확인한 뒤 원래 칸(r, c)와 바뀐 방향(nd)으로 dfs를 수행합니다.

 

3. 오른쪽으로 회전시킬 수 없으면, 왼쪽으로 회전시킨 뒤 두 칸 이동할 수 있는지 확인하고 원래 칸(r, c)와 바뀐 방향(nd)으로 dfs를 수행합니다.

 

이때, 보통의 dfs함수와 같이 방문확인 배열 boolean[][] visited; 를 사용할 필요가 없었습니다.

왜냐하면, 해당 문제에서는 왔던 경로를 되돌아 갈 수 있는 경우는 없기 때문입니다. (직진하거나, 90도 우회전, 90도 좌회전)

만약 180도 회전이 있다면 방문체크를 진행해줘야 할것 입니다.

 

dfs함수가 종료되는 경우(base case)는 다음과 같습니다.

1. 현재 진행방향으로 이동할 수 없으며

2. 오른쪽으로 회전한 방향으로 이동할 수 없고

3. 왼쪽으로 회전한 방향으로도 이동할 수 없습니다.

 

이때 저는 dfs함수를 재귀적으로 탐색할 때, if else 문을 사용하지 않고 return문으로 조건을 분기했기 때문에 dfs함수의 마지막에 return문을 적어서 base case를 구현했습니다.

 

static void find_track(int r,int c, int d){ // 현재 방향으로 두 칸 씩 이동가능한지 확인, 이동할 수 없으면 오른쪽 혹은 왼쪽으로 회전 시키기
        
        // 현재 방향으로 두 칸씩 이동이 가능한지 확인
        int nr = r, nc = c;
        int cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[d];
            nc += dc[d];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt+=1;
            }
        }
        if(cnt==2){ // 현재 방향으로 두 칸 이동이 가능함.
            track.append("A");
            find_track(nr,nc,d);
            return;
        }
        
        // 오른쪽으로 회전 시켜보기
        int nd = (d + 1) % 4;
        nr = r;
        nc = c;
        cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[nd];
            nc += dc[nd];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt += 1;
            }
        }
        if(cnt==2){
            track.append("R");
            find_track(r,c,nd);
            return;
        }

        // 왼쪽으로 회전
        nd = (d - 1)==-1 ? 3 : (d - 1);
        nr = r;
        nc = c;
        cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[nd];
            nc += dc[nd];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt += 1;
            }
        }
        if(cnt==2){
            track.append("L");
            find_track(r,c,nd);
            return;
        }

        return;
    }

 

알게된 점

• 문제의 특성에 따라서 dfs 수행 시 방문체크를 진행하지 않아도 됨을 알게되었습니다.
• 문제의 특성을 잘 파악하여, 더 효율적으로 dfs를 구현할 수 있음을 알게되었습니다.
  • 저는 처음에 전체 "#"의 갯수를 세고, dfs를 수행하며 모든 "#"을 다 탐색하면 함수를 종료하도록 구현하려 했습니다. 하지만 이렇게 할 필요 없이 더 이상 이동할 수 없는 경우 dfs를 종료하면 됐습니다.

 

전체코드

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

public class Main {

    static int H,W;
    static String[][] map;
    static int sr,sc; // 시작 좌표
    static int sd; // 시작 방향
    static int[] dr = {-1,0,1,0}; // 북, 동, 남, 서
    static int[] dc = {0,1,0,-1};
    static StringBuilder track;
    
    static boolean is_range(int r,int c){
        if(r < 0 || r>=H) return false;
        if(c < 0 || c>=W) return false;
        return true;
    }

    static String convert_dir(int d){
        if(d==0){
            return "^";
        }
        if(d==1){
            return ">";
        }
        if(d==2){
            return "v";
        }
        if(d==3){
            return "<";
        }
        return "?";
    }

    static void find_track(int r,int c, int d){ // 현재 방향으로 두 칸 씩 이동가능한지 확인, 이동할 수 없으면 오른쪽 혹은 왼쪽으로 회전 시키기
        
        // 현재 방향으로 두 칸씩 이동이 가능한지 확인
        int nr = r, nc = c;
        int cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[d];
            nc += dc[d];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt+=1;
            }
        }
        if(cnt==2){ // 현재 방향으로 두 칸 이동이 가능함.
            track.append("A");
            find_track(nr,nc,d);
            return;
        }
        
        // 오른쪽으로 회전 시켜보기
        int nd = (d + 1) % 4;
        nr = r;
        nc = c;
        cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[nd];
            nc += dc[nd];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt += 1;
            }
        }
        if(cnt==2){
            track.append("R");
            find_track(r,c,nd);
            return;
        }

        // 왼쪽으로 회전
        nd = (d - 1)==-1 ? 3 : (d - 1);
        nr = r;
        nc = c;
        cnt = 0;
        for(int i=0;i<2;i++){
            nr += dr[nd];
            nc += dc[nd];
            if(is_range(nr,nc) && map[nr][nc].equals("#")){
                cnt += 1;
            }
        }
        if(cnt==2){
            track.append("L");
            find_track(r,c,nd);
            return;
        }

        return;
    }
    
    static void find_start(){
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(map[i][j].equals("#")){
                    int cnt = 0;
                    for(int d=0;d<4;d++){
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if(is_range(nr,nc) && map[nr][nc].equals("#")){
                            cnt+=1;
                            sd = d;
                            if(cnt>1) break;
                        }
                    }
                    if(cnt==1){
                        sr = i;
                        sc = j;
                        return;
                    }
                }
            }
        }
        
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        map = new String[H][W];
        track = new StringBuilder();
        
        for(int i=0;i<H;i++){
            char[] ch = br.readLine().toCharArray();
            for(int j=0;j<W;j++){
                map[i][j] = String.valueOf(ch[j]);
            }
        }

        find_start();
        find_track(sr,sc,sd);

        System.out.printf("%d %d\n",sr+1,sc+1);
        System.out.printf("%s\n",convert_dir(sd));
        System.out.print(track.toString());
        
        
    }
}