[DFS]백준_로봇청소기

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

14503번: 로봇 청소기

이 문제를 읽었을 때는 시뮬레이션이라고 생각했다. 주어진 조건대로 그냥 코드를 짜면 된다고 생각했고

그 방법이 틀린 방법이 아니다. 실제로 많은 시뮬레이션결과로 짠 코드들이 존재했다.

이차원 평면에서 이동하는것은 그래프 탐색 or 시뮬레이션 이다. 어떤 것을 선택해서 구현하느냐는 본인의 선택이지만

제대로 된 선택을 해야 빠른시간안에 제대로 된 문제를 구현할 수 있다. 탐색의 핵심은 탐색을 해 나가는 것이다

하지만, 코드를 간결하게 하기 위해 재귀함수로 푸는 법을 찾아보게 되었다.

이 문제에서 중요한 포인트는 방향이다. 방향에 대해서만 잘 접근 하면 쉬워지는 문제이다.

다음방향을 어떻게 유도해 낼지 잘 고민해본후 연산을 통해 방향을 잘 정해주고 주어진 순서대로 해결해주었다.

 

**재귀함수를 사용해 줄때 어디서 어떻게 return해줄지를 잘 고민해봐야 한다

 

import java.util.Scanner;
 
public class Main {
    static int[][] map = new int[50][50];   //청소하는 장소
    static int count=1; //청소하는 칸의 수
    static int dx[] = {-1,0,1,0};   //행 이동을 위한 배열   //북, 동, 남, 서
    static int dy[] = {0,1,0,-1};   //열 이동을 위한 배열
    static int N,M;
     
    static void dfs(int x, int y, int d){
        int nx,ny,nd=d;
        for(int i=0;i<4;i++) { //----->왼쪽 방향부터 탐색해주는것에 대해 네방향 모두를 연산에 의해 나타낼수 있음이 키 포인트이다.
            nd = (nd+3) % 4;   //----->해당 방법을 통해 어떤 방향이든 항상 왼쪽부터 4방향을 차례로 탐색할 수 있게 된다.
            nx = x +dx[nd];
            ny = y +dy[nd];
            
            if(nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny]==1) continue; //범위가 벗어나거나 벽이면 방향전환.
            if(map[nx][ny]==0) { //청소시작.
                count++;
                map[nx][ny]=2;
                dfs(nx,ny,nd);
                return; //for문이 끝나고 아래로 코드로 내려가게 되면 갑자기 후진을 진행하게 되는 경우 발생.
            }
        }
        
        //4방향의 탐색이 모두 끝난 후.
        nd = (nd+2)%4; //후진에 대한 방향 설명.
        nx = x+dx[nd];
        ny = y+dy[nd];
        if(map[nx][ny]==1) return; //벽이면 종료.
        else dfs(nx,ny,d);
    }
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int d,x,y;
         N=sc.nextInt();
         M=sc.nextInt();
          
         x=sc.nextInt();
         y=sc.nextInt();
         d=sc.nextInt();
          
         for(int i=0;i<N;i++)    //배열 입력받음
         {
             for(int j=0;j<M;j++)
             {
                 map[i][j]=sc.nextInt();
             }
         }
         map[x][y]=2;   //처음 위치는 먼저 청소하므로 청소했다고 표시
        dfs(x,y,d);
        System.out.println(count);
 
    }
 
}