• 벽 3개를 세우는건 3중 for문으로 구현
    • 각 index는 0에서 N*M-1까지의 범위를 가지고 있고 M으로 나눈 몫은 row, 나머지는 col
  • 바이러스가 퍼지는 것은 bfs로 구현
  • 3중 for문에서 0인 위치를 벽(1)으로 만들고 다시 0으로 되돌려 놓는 과정에서 0으로 되돌려놓고는 0의 개수를 세버리는 실수를 하여 틀린 답이 계속 나왔음.
    • 하기 코드에서 countSafeNInit()과 board[r3][c3] = SAFE의 순서를 바뀌 발생했던 문제
    • 0의 개수를 먼저 세고, 1로 변경했던 걸 0으로 되돌려놔야 올바른 순서


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103



import java.io.*;
import java.util.*;

public class Main {
	static final int SAFE = 0;
	static final int WALL = 1;
	static final int VIRUS = 2;
	
	static int N, M;
	static int[][] board;
	static boolean[][] visited;
	static class Node {
		int r, c;
		Node (int r, int c) {
			this.r = r; this.c = c;
		}
	}
	
	static List<Node> virusList;
	
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = { 0,-1, 0, 1};

	static void bfs() {
		Queue<Node> q = new ArrayDeque<>();
		for (Node e : virusList) q.offer(e);

		while (!q.isEmpty()) {
			Node cur = q.poll();

			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dx[i];
				int nc = cur.c + dy[i];
				if \(nr < 0 \|| nr >= N \|| nc < 0 \|| nc >= M \|| board\[nr]\[nc] >= WALL)
					continue;

				board[nr][nc] = VIRUS;
				q.offer(new Node(nr, nc));
			}
		}
	}

	static int countSafeNInit() {
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == SAFE)
					cnt++;
				else if (board[i][j] == VIRUS)
					board[i][j] = SAFE;
			}
		}
		for (Node e : virusList)
			board[e.r][e.c] = VIRUS;

		return cnt;
	}

	static int solution() {
		int max = 0;
		for (int i = 0; i < N*M; i++) {
			int r1 = i / M, c1 = i % M;
			if (board[r1][c1] >= WALL) continue;
			board[r1][c1] = WALL;
			for (int j = i+1; j < N*M; j++) {
				int r2 = j / M, c2 = j % M;
				if (board[r2][c2] >= WALL) continue;
				board[r2][c2] = WALL;
				for (int k = j+1; k < N*M; k++) {
					int r3 = k / M, c3 = k % M;
					if (board[r3][c3] >= WALL) continue;
					board[r3][c3] = WALL;

					bfs();

					max = Math.max(max, countSafeNInit());
					board[r3][c3] = SAFE;
				}
				board[r2][c2] = SAFE;
			}
			board[r1][c1] = SAFE;
		}
		return max;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		board = new int[N][M];
		visited = new boolean[N][M];
		virusList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if (board[i][j] == VIRUS) virusList.add(new Node(i, j));
			}
		}
		System.out.println(solution());
	}
}