[백준]#1986 체스

문제

n*m 크기의 체스 판과, 상대팀의 Queen, Knight, Pawn의 위치가 주어져 있을 때, 안전한 칸이 몇 칸인지 세는 프로그램을 작성하시오. (안전한 칸이란 말은 그 곳에 자신의 말이 있어도 잡힐 가능성이 없다는 것이다.)

참고로 Queen은 가로, 세로, 대각선으로 갈 수 있는 만큼 최대한 많이 이동을 할 수 있는데 만약 그 중간에 장애물이 있다면 이동을 할 수 없다. 그리고 Knight는 2*3 직사각형을 그렸을 때, 반대쪽 꼭짓점으로 이동을 할 수 있다. 아래 그림과 같은 8칸이 이에 해당한다.

이때 Knight는 중간에 장애물이 있더라도 이동을 할 수 있다. 그리고 Pawn은 상대팀의 말은 잡을 수 없다고 하자(즉, 장애물의 역할만 한다는 것이다).

예를 들어 다음과 같이 말이 배치가 되어 있다면 진하게 표시된 부분이 안전한 칸이 될 것이다. (K : Knight, Q : Queen, P : Pawn)

입력

첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1<=n, m<=1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는
Knight의 개수와 위치, 넷째 줄에는 Pawn의 개수와 위치가 입력된다. (즉 둘째 줄~ 넷째 줄은 k,r1,c1,r2,c2,...,rk,ck 이 빈칸을 사이에 두고 주어진다는 것이다. 여기서 ri는 i번째 말의 행 위치, ci는 i번째 말의 열 위치를 의미한다.) 한 칸에는 하나의 말만 놓인다고 가정한다. Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는다.

출력

첫째 줄에 n*m 체스판에 안전한 칸이 몇 칸인지 출력하시오.

예제 입력 1

4 4
2 1 4 2 4
1 1 2
1 2 3

예제 출력 1

6

풀이

import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int N;
    static int M;
        //queen: 1, knight: 2, pawn: 3, 안전한 칸:0, 위험한 칸: 4
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N+1][M+1];

        int Q = sc.nextInt();
        for(int i=0; i<Q; i++) {
            map[sc.nextInt()][sc.nextInt()] = 1;
        }

        int K = sc.nextInt();
        for(int i=0; i<K; i++) {
            map[sc.nextInt()][sc.nextInt()] = 2;
        }

        int P = sc.nextInt();
        for(int i=0; i<P; i++) {
            map[sc.nextInt()][sc.nextInt()] = 3;
        }

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(map[i][j]==1) {
                    for(int k=0; k<8; k++)
                        dfs_queen(i, j, k);
                }

                else if(map[i][j]==2)
                    dfs_knight(i, j);
            }
        }
        int cnt=0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(map[i][j]==0)
                    cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void dfs_queen(int x, int y, int d) {
        if(d==0) {
            int X = x;
            int Y = y+1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 0);
                } else
                    return;
            }
        }

        if(d==1) {
            int X = x+1;
            int Y = y+1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 1);
                } else
                    return;
            }
        }

        if(d==2) {
            int X = x+1;
            int Y = y;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 2);
                } else
                    return;
            }
        }
        if(d==3) {
            int X = x+1;
            int Y = y-1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 3);
                } else
                    return;
            }
        }
        if(d==4) {
            int X = x;
            int Y = y-1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 4);
                } else
                    return;
            }
        }
        if(d==5) {
            int X = x-1;
            int Y = y-1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 5);
                } else
                    return;
            }
        }
        if(d==6) {
            int X = x-1;
            int Y = y;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 6);
                } else
                    return;
            }
        }
        if(d==7) {
            int X = x-1;
            int Y = y+1;

            if(X>=1 && X<=N && Y>=1 && Y<=M) {
                if (map[X][Y] == 0 || map[X][Y] == 4) {
                    map[X][Y] = 4;
                    dfs_queen(X, Y, 7);
                } else
                    return;
            }
        }
    }

    public static void dfs_knight(int x, int y) {
        if(x-1>=1 && y-2>=1 && map[x-1][y-2]==0)
            map[x-1][y-2]=4;

        if(x-2>=1 && y-1>=1 && map[x-2][y-1]==0)
            map[x-2][y-1]=4;

        if(x-1>=1 && y+2<=M && map[x-1][y+2]==0)
            map[x-1][y+2]=4;

        if(x-2>=1 && y+1<=M && map[x-2][y+1]==0)
            map[x-2][y+1]=4;

        if(x+1<=N && y+2<=M && map[x+1][y+2]==0)
            map[x+1][y+2]=4;

        if(x+2<=N && y+1<=M && map[x+2][y+1]==0)
            map[x+2][y+1]=4;

        if(x+1<=N && y-2>=1 && map[x+1][y-2]==0)
            map[x+1][y-2]=4;

        if(x+2<=N && y-1>=1 && map[x+2][y-1]==0)
            map[x+2][y-1]=4;
    }
}