백준 준규와 사과(5913)

 

오늘은 백트래킹 문제를 풀었다.

 

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

5913번: 준규와 사과

 

장애물을 제외하고 모든 경우를 진행해야하는 케이스이다 문제 조건중에서는 두 명의 포인트가 동등하게 움직여서 모든 경우를 채워야하는 조건이 붙어있다.

 

• 장애물을 제외하고 모든 경우를 지나가야한다
• 두 포인트가 동등하게 움직여 모이는 포인트를잡아야한다

 

필자의 풀이는 k는 짝수로 각 포인트가 움직여야하는 거리를 계산

 

0,0 포인트에서 해당 거리를 움직인 이후 해당 포인트에서 4,4로 진행이 가능한지 여부 체크하여 해를 구했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int answer = 0;
    static int distance = 0;
    static int[][] dir = { {0,1}, {0,-1}, {1,0}, {-1,0} };
    static boolean[][] block = new boolean[5][5];

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        for (int i=0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            block[n1-1][n2-1] = true;
        }

        distance = (25 - N) / 2;
        dfs(0, 0, new boolean[5][5], 0, false);
        System.out.println(answer);
    }

    public static void dfs(int x, int y, boolean[][] visited, int loc, boolean flag) {
        if (loc == distance) {
            if (!flag) {
                dfs(x, y, visited,0, true);
            } else if (x == 4 && y == 4) {
                answer++;
            }
            return;
        }

        visited[x][y] = true;
        for (int i=0; i < dir.length; i++) {
            int x1 = x + dir[i][0];
            int y1 = y + dir[i][1];
            if (isTrue(x1, y1, visited)) {
                dfs(x1, y1, visited, loc + 1, flag);
            }
        }
        visited[x][y] = false;

    }

    public static boolean isTrue(int x, int y, boolean[][] visited) {
        if (x >=0 && y >=0 && x < 5 && y < 5 && !visited[x][y] && !block[x][y]) {
            return true;
        }
        return false;
    }


}

 

결과