[문제풀이] 백준 14503번 로봇청소기 +복습

[풀이 방법]

Main(){

N,M,x,y,d 값 입력 

배열 입력

처음의 위치에 방문 표시

DFS();

print(결과);

}

DFS(x,y,d){

1. 주변에 방문할 칸이 있는 경우

- 방향을 4방향으로 바꾸면서 방문할 수 있으면 방문 후 표시

- 방문 후 DFS() 호출, 결과++;

- 리턴

2. 방문할 칸이 없는 경우

- 후진

  > 후진했는데 벽인 경우   :    종료

  > 후진 가능한 경우 :  후진한 위치를 기준으로 DFS() 호출

[작성한 코드]

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 cx, cy, cd=d; //현재 함수 내의 x,y,d 값 저장을 위한 변수 for(int i=0;i<4;i++){ //총 4방향으로 이동할 수 있으므로 4번 돌림 cd=(cd+3)%4; //방향을 바꾸기 위한 식 // 북,서,남,동(0,3,2,1) 순서로 변경 cx=x+dx[cd]; cy=y+dy[cd]; // 머리를 둔 방향으로 한칸 이동 if(cx>N-2 || cx<1 || cy>M-2 || cy<1 || map[cx][cy]==1) //이동한 칸이 벽이면 continue; //위로 돌아가서 방향 바꿈 if(map[cx][cy]==0){ //청소 안한 칸이면 count++; //청소하고 카운트 증가 map[cx][cy]=2; //청소했다고 표시 dfs(cx,cy,cd); //다음칸 방문을 위해 dfs함수 호출 return; } } //4방향의 칸 중 방문할 칸이 없으면 cd=(d+2)%4; // 후진을 위한 방향 설정 // 후진 cx=x+dx[cd]; cy=y+dy[cd]; if(map[cx][cy]==1) //후진한 곳이 벽이면 리턴 return; else //아니면 dfs(cx,cy,d); //현재 위치와 기존의 방향으로 dfs함수 호출 } 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); } }

[복습코드]

import java.util.Scanner; public class Main { static int N,M; static int map[][]; static int clean[][]; static int ran=0; static int dx[]={-1,0,1,0}; static int dy[]={0,1,0,-1}; public static void main(String args[]){ Scanner sc = new Scanner(System.in); N=sc.nextInt(); M=sc.nextInt(); int r=sc.nextInt(); int c=sc.nextInt(); int d=sc.nextInt(); map=new int[N][M]; clean=new int[N][M]; for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ map[i][j]=sc.nextInt(); } } dfs(r,c,d); System.out.println(ran); } static void dfs(int x, int y, int d){ if(clean[x][y]==0) clean[x][y]=++ran; int cd = d; //int cnt=0; boolean status=true; while(true){ if(cd!=0) cd=cd-1; else cd=3; int nx=dx[cd]+x; int ny=dy[cd]+y; if(nx>=0 && nx<N && ny>=0 && ny<M && map[nx][ny]==0 && clean[nx][ny]==0){ dfs(nx,ny,cd); break; } else{ if(cd==d){ //System.out.println(cd); status=false; break; } } } if(status==false){ if(d==3 || d==2){ int cx=dx[d-2]+x; int cy=dy[d-2]+y; if(cx>=0 && cx<N && cy>=0 &&cy<M && map[cx][cy]==0) dfs(cx,cy,d); else return; } if(d==0 || d==1){ int cx = dx[d+2]+x; int cy = dy[d+2]+y; if(cx>=0 && cx<N && cy>=0 && cy<M && map[cx][cy]==0) dfs(cx,cy,d); else return; } } } }