농부 존은 최근에 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)방의 불을 켜고 끌 수 있다는 의미이다. 한 방에 여러개의 스위치가 있을 수 있고, 하나의 불을 조절하는 스위치 역시 여러개 있을 수 있다.
베시가 불을 켤 수 있는 방의 최대 개수를 출력하시오.
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
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;
}
}
}