[BOJ_14503 | DFS] 로봇 청소기

풀이

삼성 SW 역량 테스트 기출문제로, DFS의 간단한 응용 능력을 물어보는 문제였던 것 같다.

DFS를 수행하는 방법이야 재귀를 이용해서 처리하면 되지만, 이 문제의 경우에는 

DFS를 실행하는 순서를 처리하는 방식이 살짝 까다로운 부분이 있었다. 

우선, 문제에서 제시한 방향에 따라 direction변수를 설정해 주었다.

0 - North

1 - East

2 - South

3 - West

그리고 LeftRotate의 경우 direction변수가 들어왔을 때 그 방향의 왼쪽으로 회전한 방향을 출력하도록 처리하였다.

예를 들어, 0이 들어오면 북쪽의 좌회전 방향인 서쪽을 가리키는 3을 출력하는 식이다.

그리고 dx[], dy[] 배열을 선언하고, 제시한 방향에 맞게 x, y를 변화시키는 값을 저장하였다.

예를 들어 dx[0], dy[0]은 x, y를 가지는 점을 북쪽으로 한칸 이동시키는 값을 저장하는 식이다.

따라서, x+dx[0], y+dy[0]의 경우에는 x, ,y 를 북쪽으로 한 칸 이동시키게 된다.

getBackPosition의 경우 입력으로 들어온 방향의 반대 방향을 LeftRotate와 마찬가지로 출력한다.

이렇게 세팅을 마친 후에 문제에 주어진 4가지 규칙을 적용하여 문제를 해결하였다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_14503 {
 
    static int[][] map;
    static int n, m, cnt, visitCount, cnt2;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean flag;
 
    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());
 
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()); cnt = 0; visitCount = 0;flag = false;cnt2=0;
        int sx = Integer.parseInt(st.nextToken());
        int sy = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        // 0 - North 1 - East 2 - South 3 - West
 
        //input map
        map = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        Search(sx, sy, d);
 
        bw.write(cnt+"\n");
        bw.flush();
        bw.close();
    }
    public static void Search(int x, int y, int d){
        if(flag) return;
        // First Rule
        if(map[x][y] == 0){cnt++; map[x][y] = 2;}
        // Second Rule
        int direction = leftRotate(d); visitCount++;
        // case 1
        if(isValid(x+dx[direction], y+dy[direction]) && map[x+dx[direction]][y+dy[direction]] == 0){
            visitCount = 0;
            Search(x+dx[direction], y+dy[direction], direction);
            return;
        }else if(isValid(x+dx[direction], y+dy[direction]) && map[x+dx[direction]][y+dy[direction]] != 0){
           if(visitCount == 4){
               visitCount = 0;
               int back = getBackPosition(direction);
               if(isValid(x+dx[back], y+dy[back]) && map[x+dx[back]][y+dy[back]] == 1){flag = true; return;}
               else{
 
                   Search(x+dx[back], y+dy[back], direction);
                   return;
               }
           }
           Search(x, y, direction);
        }
    }
    public static int leftRotate(int d){
        switch(d){
            case 0: return 3;
            case 1: return 0;
            case 2: return 1;
            case 3: return 2;
            default: return -1;
        }
    }
    public static int getBackPosition(int d){
        switch(d){
            case 0: return 2;
            case 1: return 3;
            case 2: return 0;
            case 3: return 1;
            default: return -1;
        }
    }
    public static boolean isValid(int x, int y){
        if(x>=0 && x<n && y>=0 && y<m) return true;
        return false;
    }
    public static void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                System.out.print(map[i][j]+" ");
            }System.out.println();
        }System.out.println();
    }
    public static void printD(int d){
        switch(d){
            case 0: System.out.println("North"); return;
            case 1: System.out.println("East"); return;
            case 2: System.out.println("South"); return;
            case 3: System.out.println("West"); return;
        }
    }
}