[백준/JAVA] 9944번: NxM 보드 완주하기

📖 문제

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

 

 

 

💡  풀이 방식

• 백트래킹

1. 값을 입력받으면서 격자 안의 값이 장애물(*)인 경우, 방문 처리하고 방문한 칸의 갯수(cnt)를 1 증가시킨다.

2. 한 칸만 빈 칸인 경우, 해당 케이스의 이동 경로 수는 0이다.

if(cnt == N*M)  answer = 0; // 한 칸만 빈 칸인 경우

 

 

3. 모든 칸을 탐색하며 방문한 적 없는 점에서,

4방향 탐색을 통해 1) 격자 범위 내에 있고, 2) 방문하지 않은 칸을

이동 처리했다가 안 했다가 하며 이동 경로 수를 구한다. (백트래킹)

for(int i = 0 ; i < N ; i++) {
    for(int j = 0 ; j < M ; j++) {
        if(visited[i][j])   continue;

        for(int d = 0 ; d < 4 ; d++) {
            if(!isValid(i + dx[d], j + dy[d])) continue;

            visited[i][j] = true;
            search(i, j, result, d, cnt);
            visited[i][j] = false;
        }
    }
}

 

 

[백트래킹 함수]

- 인자 : x좌표, y좌표, 이동 횟수(result), 방향 번호(dir), 방문 갯수(cnt)

search(int i, int j, int result, int dir, int cnt)

 

- (종료 조건) 모든 빈 칸을 방문한 경우 > 정답이 -1이거나 이동 횟수가 정답보다 크다면, 정답을 이동 횟수로 갱신한다.

if(cnt == N*M) {    // 모든 빈 칸 방문한 경우
    if(answer == -1 || answer > result) {
        answer = result;
        return;
    }
}

 

- 그 외의 경우, 현재 좌표(i,j)에서 현재 이동 방향(dir)으로 이동 가능하다면, 다음 지점에 대해 방문했다가/ 안 했다가 하는 경우의 수를 갱신하며 이동을 진행한다. // 만약 이동할 수 없다면, 방향을 변경한 상태에서 방문 여부를 갱신하며 이동을 진행한다.

int x = i + dx[dir];
int y = j + dy[dir];

if(isValid(x, y)) {
    visited[x][y] = true;
    search(x, y, result, dir, cnt + 1); // 방문한 킨 갯수 +1
    visited[x][y] = true;
}
else {  // 방향 변경
    for(int d = 0 ; d < 4 ; d++) {
        if(d == dir) continue;

        int nx = i + dx[d];
        int ny = j + dy[d];

        if(isValid(nx, ny)) {
            visited[nx][ny] = true;
            search(nx, ny, result + 1, dir, cnt + 1);	// 이동 횟수와 방문한 칸 갯수 +1
            visited[nx][ny] = true;
        }
    }
}

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static char[][] map;
    static boolean[][] visited;
    static int answer;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int idx = 0;
        String input = "";
        
        while((input = br.readLine()) != null) {
            idx++;
            answer = -1;
            
            st = new StringTokenizer(input);
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            
            map = new char[N][M];
            visited = new boolean[N][M];
            
            int result = 1; // 이동 횟수
            int cnt = 1; // 방문 개수
            
            for(int i = 0 ; i < N ; i++) {
                String str = br.readLine();
                for(int j = 0 ; j < M ; j++) {
                    map[i][j] = str.charAt(j);
                    
                    if(map[i][j] == '*') { // 장애물인 경우
                        visited[i][j] = true;
                        cnt++;
                    }
                }
            }
            
            // 한 칸만 빈 칸인 경우
            if(cnt == N*M)  answer = 0;
            
            for(int i = 0 ; i < N ; i++) {
                for(int j = 0 ; j < M ; j++) {
                    if(visited[i][j])   continue; // 장애물인 경우, pass
                    
                    for(int d = 0 ; d < 4 ; d++) { // 빈 칸(.)인 경우, 4방향 탐색
                        if(!isValid(i + dx[d], j + dy[d])) continue;
                        
                        visited[i][j] = true;
                        search(i, j, result, d, cnt);
                        visited[i][j] = false; // 지나온 길 되돌아가기
                    }
                }
            }
            
            System.out.println("Case " + idx + ": " + answer);
        }
    }
    
    //                          x좌표, y좌표, 이동 횟수, 방향 번호, 방문한 칸 개수
    private static void search(int i, int j, int result, int dir, int cnt) {
        // [종료 조건] 모든 빈 칸을 방문한 경우
        if(cnt == N*M) {
            if(answer == -1 || answer > result) {
                answer = result;
                return;
            }
        }
        
        int x = i + dx[dir];
        int y = j + dy[dir];
        
        if(isValid(x, y)) {
            visited[x][y] = true;
            search(x, y, result, dir, cnt + 1);
            visited[x][y] = false; // 지나온 길 되돌아가기
        }
        else {  // 방향 변경
            for(int d = 0 ; d < 4 ; d++) {
                if(d == dir) continue;
                
                int nx = i + dx[d];
                int ny = j + dy[d];
                
                if(isValid(nx, ny)) {
                    visited[nx][ny] = true;
                    search(nx, ny, result + 1, d, cnt + 1);
                    visited[nx][ny] = false; // 지나온 길 되돌아가기
                }
            }
        }
    }
    
    private static boolean isValid(int x, int y) {
        if(x < 0 || x >= N || y < 0 || y >= M)  // 보드 범위를 벗어난 경우
            return false;
        if(visited[x][y])   // 이미 방문한 경우
            return false;
        return true;   
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 백트래킹 함수 부분이 좀 다르다. 한 쪽 방향으로 계속 진행하다가 다음 방향으로 넘어가고 이런 식으로 하게 하셨다.

 

[BOJ 9944] NxM 보드 완주하기 (Java)

 

 

- 상하좌우 방문하지 않는 최대 위치를 반환하는 메소드를 일일이 구현하셨다.  (비추)

 

[Java] 백준 9944 (NxM 보드 완주하기) Gold 3

 

- 이 코드가 내가 제출한 코드랑 비슷한데 개인적으로는 이해하기 좀 더 좋았던 듯,,✅

[백준] G3 9944 NxM 보드 완주하기 (java)

---

💦 어려웠던 점

- BFS로 풀 생각을 했지, 백트래킹 쓸 생각은 하지 못 했다.

- 입력이 언제 끝날줄 알고 N과 M입력은 어떻게 받지?의 문제

 

🧐 새로 알게 된 내용

- 해당 칸을 방문하고 길을 되돌아가기 위해 백트래킹으로 푸는 문제라고 이해했다.

- TC개수 정해지지 않고, while문으로 조건 만족 시 계속 작동하도록 하는 방법

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[Baekjoon] 9944_NxM 보드 완주하기