[백준 / BOJ] 9944 N*M 보드 완주하기

문제

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

9944번: NxM 보드 완주하기

N*M크기의 보드에 장애물(*) 빈칸(.)이 있다

 

보드의 빈칸위에 놓인 공은 다음 규칙에따라 움직인다.

• 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
• 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을때 끝난다.

 

모든 빈칸을 방문하기위한 이동횟수의 최솟값을 구하는 문제다.

(모든 빈칸을 방문하지 못한다면 -1 출력)

 

---

풀이

백트래킹 구현 문제다.

N,M이 30이라서 문제에서 시키는대로 구현하면 풀린다.

단, 공이 어느 위치에서든 시작할수있으므로, N*M그리드의 모든 빈칸에서 시작시켜야함에 주의하자.

 

백트래킹 소스코드

	private int move(Pos pos, int cnt, int moveNum){
        if(pos.y < 0 || pos.y >= N || pos.x < 0 || pos.x >= M) return 987654321;
        if(cnt == this.cnt || moveNum >= ans) return moveNum;
        int ret = ans;
        int headY = pos.y+dy[pos.dir];
        int headX = pos.x+dx[pos.dir];
        if(headY < 0 || headY >= N || headX < 0 || headX >= M || check[headY][headX] || arr[headY][headX] == '*'){
            for(int i = 0; i < 4; i++){
                if(pos.dir == i) continue;
                int nextY = pos.y + dy[i];
                int nextX = pos.x + dx[i];
                int nextMoveNum = moveNum+1;
                if(nextY < 0 || nextY >= N || nextX < 0 || nextX >= M || check[nextY][nextX] || arr[nextY][nextX] == '*')
                    continue;
                check[nextY][nextX] = true;
                ret = Math.min(ret, move(new Pos(nextY, nextX, i), cnt+1, nextMoveNum));
                check[nextY][nextX] = false;
            }
        }
        else if(headY >= 0 && headY < N && headX >= 0 && headX < M ){
            check[headY][headX] = true;
            ret = Math.min(ret, move(new Pos(headY, headX, pos.dir), cnt+1, moveNum));
            check[headY][headX] = false;
        }
        return ret;
    }

 

EOF처리를 상당히 오랫동안 했는데, 이상하게 내 컴파일 환경에서는 null일경우 종료처리를 해줘도 NumberFormatException을 뿜으며 종료되었다.. 몇번해보다 안되서 그대로 제출했더니 백준에서는 AC가 나옴

 

(다른사람 AC코드를 가져와서 내 컴파일러에서 돌려봐도 이상한 예외를 뿜으며 종료된다.)

 

---

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9944%20N*M%20%EB%B3%B4%EB%93%9C%20%EC%99%84%EC%A3%BC%ED%95%98%EA%B8%B0/Main.java 

devxb/JJUNalgo