[DFS, BFS] BOJ_5913 준규와 사과

문제

대학교를 졸업한 준규는 농부의 꿈을 이루기 위해서 가로 5m, 세로 5m 크기의 땅을 구입했다. 준규는 땅을 가로 1m, 세로 1m 크기로 구역을 나누었다. 가장 왼쪽 위 칸은 (1,1)이고 가장 오른쪽 아래 칸은 (5,5)이다. 준규의 땅을 아래 그림과 같이 나타낼 수 있다.

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

구역 K개를 제외한 각각의 구역에는 사과 나무가 하나씩 심어져 있다. K개 구역에는 거대한 돌이 있기 때문에 사과 나무가 심어져 있지 않다.

사과를 수확하는 일은 매우 귀찮은 일이다. 따라서, 준규는 친구 해빈이와 함께 재밌는 방법으로 수확을 하려고 한다.

준규는 (1,1)에서 사과를 수확하기 시작하고, 해빈이는 (5,5)에서 시작한다. (1,1)과 (5,5)에는 항상 사과 나무가 심어져 있다.

사과 나무 하나에 있는 모든 사과를 수확하는데 걸리는 시간은 항상 30분이다. 준규와 해빈이가 현재 있는 칸의 사과 나무에서 사과를 모두 수확하면, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다. 이동하는데 걸리는 시간도 30분이다.

준규와 해빈이는 준규의 땅에 있는 모든 사과를 수확할 것이고, 마지막에는 같은 칸에서 만나려고 한다. 이 때, 이렇게 사과를 수확하는 방법의 수를 구하는 프로그램을 작성하시오.

두 사람은 항상 사과가 있는 칸으로만 이동하며, 이미 수확을 마친 사과 나무가 있는 칸으로는 이동하지 않는다. 또, 마지막을 제외하고 같은 칸에서 만날 수는 없다.

입력

첫째 줄에 K가 주어진다. 둘째 줄부터 K (0 ≤ K ≤ 22, K는 짝수)개 줄에는 사과 나무가 없는 칸의 위치 (i,j)가 주어진다.

출력

문제에서 주어진 방법대로 사과를 모두 수확하는 방법의 수를 출력한다.

예제 입력 

4
3 2
3 3
3 4
3 1

예제 출력 

1

힌트

입력으로 주어진 상황을 그림으로 그리면 아래와 같다. 점(.)은 사과 나무가 있는 칸, x는 없는 칸을 나타내며, j는 준규의 위치, h는 해빈이의 위치이다.

j  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  h

문제의 조건을 지키면서 사과를 모두 수확하는 방법은 한가지이며, 아래와 같다.

j  j--j  j--j
|  |  |  |  |
j--j  j--j  j
            |
x  x  x  x j/h
            |
h--h--h--h--h
|
h--h--h--h--h

코드

package dfs;
 
import java.util.Scanner;
 
/**
 * https://www.acmicpc.net/problem/5913
 * 준규와 사과
 * DFS
 * @author minjung
 */
 
public class baekjoon_5913 {
    
    static int count = 0;
    static int[][] map = new int[5][5]; // 농장
    static int K;
    static int max = 0;
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        
        K = sc.nextInt();
        
        for ( int i = 0; i < K; i++ ){
            int x = sc.nextInt();
            int y = sc.nextInt();
            map[x-1][y-1] = -1; // 돌덩이 표시 - 갈 수 없음
        }
        
        DFS(0,0,1);
        
        System.out.println(count);
        
    }
    
    private static void DFS( int x, int y, int size ){
        if ( x == 4 && y == 4 ){
            if ( size == 25-K ){
                count++;
            }
            if ( max < size ){
                max = size;
            }
        }
        map[y][x] = -1; 
        
        if (y > 0 && map[y - 1][x] != -1)
            DFS(x, y - 1, size + 1);
          // 아래로 이동할 수 있다면 이동!
        if (y < 4 && map[y + 1][x] != -1)
            DFS(x, y + 1, size + 1);
          // 왼쪽으로 이동할 수 있다면 이동!
        if (x > 0 && map[y][x - 1] != -1)
            DFS(x - 1, y, size + 1);
          // 오른쪽으로 이동할 수 있다면 이동!
        if (x < 4 && map[y][x + 1] != -1)
            DFS(x + 1, y, size + 1);
 
        map[y][x] = 0; // 지나간 자리 원상태로 되돌리기
    }
 
}