백준 14503

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

14503번: 로봇 청소기

바보같이 이동 방향 배열 순서를 잘못 정의해서 한참 고민한 문제... 

난이도는 삼성 기출중에 그래도 쉬운 편에 속하는것 같은데 오래 걸렸다....북-동-남-서 방향으로 가야하는데 아무 생각없이 동서남북으로 정의해뒀어서😂

 

🍇 케이스 정의

#1) 현재칸이 0인 경우 -> clean()

#2) 주변 4칸에 청소가 되지 않은 빈칸이 있는지 탐색한다 -> findAround()

#2-1) 주변 4칸 중 청소 가능한 칸이 있다면 (findAround() == true) 현재 방향 기준 반시계방향으로 방향을 틀면서 가능한 위치로 이동한다. (goToClean)

#2-2) 주변 4칸이 다 청소되거나 벽이라면 후진을 시도한다(goBack()) 

후진 안되는 경우에는 탐색을 종료하고 정답을 출력한다.

 

 

 

🍇 메소드 목록 

- 메인함수

- 탐색용 함수 (BFS / DFS 둘다 써봤고 채점 해봤는데 DFS가 공간 효율적인 측면에서 조금 더 좋았다. 두 메소드 다 코드에 넣어둠)

- 청소 : 해당 칸을 -1로 바꾼다. 참고로 1로 바꾸면 후진할때 갈 수 있는데 못간다고 판정할 수 있으므로 0,1말고 다른 값으로 바꾸면 된다. 난 그냥 -1로 해둠 

- 주변 4칸 중 청소 가능한 칸 있는지 탐색하는 findAround() : true/false따라 2-1로갈지 2-2로 갈지 결정

- 2-1의 경우 goToClean() : 반시계방향으로 틀면서 가능한 위치로 move() 

- 2-2의 경우 goBack() : 뒷 칸이 벽이 아닌지 확인후 move()  [ 또는 isFinished() = true -> bfs쓸때 필요해서 선언해둠, DFS는 재귀형태라 굳이 필요 없을 것 같다 ]

---

🍇 코드 내용 

1. 메인 함수 및 static 변수들 선언

    static int[] dirX = { -1, 0, 1, 0 };
    static int[] dirY = { 0, 1, 0, -1 };
    static int[][] room;
    static int n, m, answer;
    static int curX, curY, curDir;
    static boolean isFinished = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        answer = 0;
        room = new int[n][m];

        // 현재 좌표, 보고 있는 방향 설정
        st = new StringTokenizer(br.readLine());
        curX = Integer.parseInt(st.nextToken());
        curY = Integer.parseInt(st.nextToken());
        curDir = Integer.parseInt(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                room[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        DFS(curX, curY);
        // 또는 BFS(curX, curY);
        System.out.println(answer);
    }

2. DFS 함수

첨에 BFS 써야할 것 같다고 생각했다. 실제로 저 코드로 구현해놓고 BFS재귀적으로 계속 호출을 하게끔 돌렸는데 답이 나오긴한다. 그치만 공간 메모리 규모는 DFS가 더 좋기도 하고 ... 굳이 최단 경로 찾는건 아니어서 DFS로 푸는 듯 하다. 코드도 DFS가 더 간결... 

 

flag 가 주변 4칸 중 가도 되는 곳이 있냐?! 를 나타내는 변수이므로 이거에 따라서 청소하러 갈지(goToClean()), 후진할지 (goBack()) 결정! 

참고로 방문 여부는 청소한 상태 == -1이면 이미 간거니까 0일때만 이동하게끔 하면 된다. 

/* public static void BFS(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        int [] pos = { x, y };
        queue.add(pos);

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int tempX = poll[0];
            int tempY = poll[1];

            if (room[tempX][tempY] == 0) {
                clean(tempX, tempY);
            }
            boolean flag = findAround(tempX, tempY);
            if (flag) {
                goToClean();
                int[] temp = { curX, curY };
                queue.add(temp);
            } else {
                goBack();
                if (isFinished) {
                    break;
                }
            }
        }
    } */
    
public static void DFS(int x, int y) {
        if (room[x][y] == 0) {
            clean(x, y);
        }
        boolean flag = findAround(x, y);
        if (flag) {
            goToClean();
        } else {
            goBack();
        }
}

3. 해당 칸 청소하는 함수 / 주변 칸 탐색하는 함수 / 유효한 좌표인지 확인하는 함수( 지도상의 크기가 혹시 넘어가지 않도록? ) 

public static void clean(int x, int y) {
        room[x][y] = -1;
        answer += 1;
    }

// 주변 4칸 중 청소되지 않은 빈 칸이 있는지 없는지 여부 확인
public static boolean findAround(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextX = x + dirX[i];
            int nextY = y + dirY[i];
            if (validPos(nextX, nextY)) {
                if (room[nextX][nextY] == 0) {
                    // 청소되지 않은 빈칸
                    return true;
                }
            }
        }
        return false;
}

public static boolean validPos (int x, int y) {
	if (x < 0 || x >= n || y < 0 || y >= m) {
            return false;
    }
    return true;
}

4. 이동시키는 함수, 2-1,2 처리하는 goToClean() & goBack()

move에 굳이 dir 안 들어가도 될 것 같다...차피 curDir은 static 이라 상관 없을 듯 

public static void move(int x, int y, int dir) {
        curX = x;
        curY = y;
        curDir = dir;
        DFS(curX, curY);
}

방향 돌릴 때는 3더하고 나머지 4 연산해주면 된다

public static void goToClean() {
        int tempDir = curDir;
        // 반시계 방향 회전
        for (int i = 0; i < 4; i++) {
            tempDir = (tempDir + 3) % 4;
            int nextX = curX + dirX[tempDir];
            int nextY = curY + dirY[tempDir];
            
            if (validPos(nextX, nextY)) {
                if (room[nextX][nextY] == 0) {
                    curDir = tempDir;
                    move(nextX, nextY, curDir);
                    break;
                }
            }
        }
}

    // 주변에 청소되지 않은 빈칸 없어서 후진해야하는 경우
    // curDir은 바꾸지 않는다.
public static void goBack() {
        int nextX = curX - dirX[curDir];
        int nextY = curY - dirY[curDir];

        if (!validPos(nextX, nextY) || room[nextX][nextY] == 1) {
            isFinished = true;
        }
        else {
            move(nextX, nextY, curDir);
        }
}