[백준]#11967 불켜기

문제

농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.

베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.

베시가 불을 켤 수 있는 방의 최대 개수를 구하시오.

입력

첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다.

다음 M줄에는 네 개의 정수 x, y, a, b가 주어진다. (x, y)방에서 (a, b)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.

출력

베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.

예제 입력 1

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

예제 출력 1

5

풀이

이 문제는 DFS 알고리즘을 이용해서 풀 수 있는 문제였다. 처음에 어렵게 생각해서 복잡한 코드를 짜려했는데 코딩을 하다보니 간단한 문제였다.

import java.io.InputStreamReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.ArrayList;

public class Main {
    static ArrayList<Pair>[][] map;
    static int[][] lighten;
    static boolean[][] visited2;
    static boolean[][] visited;
    static int N;
    static boolean flag;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        map = new ArrayList[N+1][N+1];
        visited = new boolean[N+1][N+1];
        visited2 = new boolean[N+1][N+1];
        lighten = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++)
                map[i][j] = new ArrayList<>();
        }

        for(int i=0; i<M; i++) {
            input = br.readLine().split(" ");
            map[Integer.parseInt(input[0])][Integer.parseInt(input[1])].add(new Pair(Integer.parseInt(input[2]), Integer.parseInt(input[3])));
        }

        visited[1][1] = true;
        lighten[1][1] = 1;
        lighting(1, 1);

        while(true) {
            flag = false;
            visited2 = new boolean[N+1][N+1];
            dfs(1, 1);

            if(!flag) break;
        }

        int ans = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(lighten[i][j]==1)
                    ans++;
            }
        }
        System.out.println(ans);
    }

    public static void lighting(int x, int y) {
        for(int i=0; i<map[x][y].size(); i++) {
            Pair p = map[x][y].get(i);
            lighten[p.x][p.y] = 1;
        }
    }

    public static void dfs(int x, int y) {
        if(!visited[x][y]) {
            flag = true;
            visited[x][y] = true;
            lighting(x, y);
        }
        visited2[x][y] = true;

        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];

            if(nx<1 || nx>N || ny<1 || ny>N || lighten[nx][ny]==0 || visited2[nx][ny]) continue;

            visited2[nx][ny] = true;
            dfs(nx, ny);
        }
    }

    public static class Pair {
        int x;
        int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}