[백준 14503] 로봇 청소기 -JAVA //le_effort//

삼성 SW 역량테스트 문제.

 

이 문제는 푸는 방법이 여러 개 인 것 같다.

블로그를 시작하기 전에 한 번 풀어봤었는데 이번에 새로 풀고 나서 기존 코드와 비교를 해보니 풀이 방법이 조금 달랐다.

 

차근차근 조건을 살펴보자

 

1. 현재 위치를 청소한다. (나는 visited 배열로 청소를 했다 하면 방문 표시를 했다.)

2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례로 탐색을 진행한다.

 

문제의 조건에서 

d = 0 북

d = 1 동

d = 2 남

d= 3  서

 

이렇게 주어지는데  북쪽을 기준으로 왼쪽으로 진행하면

북-> 서 -> 남 -> 동 -> 북 -> 이런 방향으로 진행이 된다.

 

이 방향이 이해가 안된다면 내가 그쪽 방향에 서있는 걸 상상해 보거나 실제로 그쪽 방향으로 서보길 바란다

 

자 이제 문제의 조건에서 주어진 d를 기준으로 방향을 정해보자

 

북->서->남->동-> 북  을 숫자로 표현하면

0->3->2->1->0

 

규칙이 보이는가?

방향이 0 일때만 3으로 바꿔주고 나머지는 기존 방향에서 -1을 진행하면 된다.

 

이제 방향을 정했으니 청소를 진행해보자.

a. 왼쪽 방향에 아직 청소하지 않은 공간이 있다면 그 방향으로 회전한 다음 한 칸 전진하고 1번부터 진행한다.

 

우선 해줘야 할 건 dx[] 와 dy [] 배열의 설정이다

 int dx[] = {-1,0,1,0};
 int dy[] = {0,1,0,-1};

 

이 dx[] 와 dy []의 값은 문제에서 주어진 d의 방향대로 했다.

d가 0일때 북쪽이니 인덱스를 -1,0 해주면 북쪽으로 진행이 된다.

 

그리고 주의 할 게 있는데 바로 왼쪽 방향에 청소하지 않은 공간이 있어야 한다

예를 들어 진행 방향이 <--   일 때

청소함 청소안함 로봇청소기

이러한 경우는 해당이 되지 않는다 "바로" 왼쪽 방향에 청소하지 않은 공간이 있어야 한다.

 

if(d==0) {
                    change_d = 3;
                }
                else {
                    change_d = d-1;
                }
                int nx = x+dx[change_d];
                int ny = y+dy[change_d];
                if(map[nx][ny]!=1 && !visited[nx][ny]) {
                    cnt =0;
                    q.add(new Node(nx,ny,change_d));
                    visited[nx][ny] = true;
                }

이게 a번의 진행방향이다.

 

조건 b는 왼쪽 방향에 청소할 공간이 없다면 그 방향으로 회전하고 2번으로 돌아간다 인데

 

이제 조건 b와 조건 c를 어떻게 연결하는지 모르는 사람들이 있을 수도 있다.

나는 조건 b를 실행할 때 cnt를 1 증가했다. 코드부터 보자

 

 

if(flag) {
                int change_d;
                visited[x][y]= true;
                if(d==0) {
                    change_d = 3;
                }
                else {
                    change_d = d-1;
                }
                int nx = x+dx[change_d];
                int ny = y+dy[change_d];
                if(map[nx][ny]!=1 && !visited[nx][ny]) {
                    cnt =0;
                    q.add(new Node(nx,ny,change_d));
                    visited[nx][ny] = true;
                }
                else {
                    cnt++;
                    q.add(new Node(x,y,change_d));
                }
            }

위 구문은 조건 c와 d를 한 번에 담은 것이다

조건 c는 종료 조건이고 문제의 조건 그대로를 구현한 것이라 어려울 것이 없고

 

조건 d는 후진을 하면 cnt를 0으로 또 바꿔줘야 한다.

cnt란 로봇청소기가 왼쪽 방향에 청소할 경우가 없는 횟수 이니깐

 

전체 코드

 

 

import java.io.*;
import java.util.*;
public class Main {
    static int n,m;
    static int map[][];
    static int ans=0;
    static int d;
    static boolean visited[][];
    static int cnt =0;
    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,1,0,-1};
    static Queue<Node> q = new LinkedList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        map = new int[n][m];
        visited = new boolean[n][m];
        
        String start_info[] = br.readLine().split(" ");
        int start_r = Integer.parseInt(start_info[0]);
        int start_c = Integer.parseInt(start_info[1]);
        int start_d = Integer.parseInt(start_info[2]);
        q.add(new Node(start_r,start_c,start_d));
        
        for(int i=0; i<n; i++) {
            String[] input = br.readLine().split(" ");
            for(int j=0; j<m; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        
        bfs();
    }
    public static void bfs() {
        while(!q.isEmpty()) {
            boolean flag = true;
            Node a= q.poll();
            int x = a.x;
            int y= a.y;
            int d= a.d;
            if(cnt ==4) {
                flag = false;
                x -=dx[d];
                y-=dy[d];
                if(map[x][y]==1) {
                    for(int i=0; i<n; i++) {
                        for(int j=0; j<m; j++) {
                            if(visited[i][j]) {
                                ans++;
                            }
                        }
                    }
                    System.out.println(ans);
                    break;
                }
                else {
                    cnt=0;
                    q.add(new Node(x,y,d));
                }
            }
            if(flag) {
                int change_d;
                visited[x][y]= true;
                if(d==0) {
                    change_d = 3;
                }
                else {
                    change_d = d-1;
                }
                int nx = x+dx[change_d];
                int ny = y+dy[change_d];
                if(map[nx][ny]!=1 && !visited[nx][ny]) {
                    cnt =0;
                    q.add(new Node(nx,ny,change_d));
                    visited[nx][ny] = true;
                }
                else {
                    cnt++;
                    q.add(new Node(x,y,change_d));
                }
            }
        }
    }
}
class Node{
    int x,y,d;
    Node(int x, int y, int d){
        this.x=x;
        this.y=y;
        this.d=d;
    }
}