[Java] 백준 1724 - 그림판

문제

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

 

문제에 나와있지는 않지만 Sx = Ex이거나 Sy = Ey라는 조건이 있다는 것 같다. (= 대각선은 없다는 뜻)

---

풀이

대각선이 없다는 가정하에는 구역만 잘 나눠주고 각 구역마다 Flood Fill (BFS)만 돌려주면 된다.

구역을 나눌때는 선을 칸으로 생각하면 쉽다. 예를 들어 예제 입력 1 같은 경우는 다음과 같은 배열을 만들어서 활용하면 된다. 물론 이렇게 하면 배열의 크키가 4배가 되어서 시간/메모리 효율성은 조금 떨어지겠지만, 어차피 N, M 값이 작고 전체적인 구현이 단순해져서 좋다.  

---

코드

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

public class Main {
	public static class Pos {
		public int row, col;

		public Pos(int r, int c) {
			row = r;
			col = c;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		boolean[][] board = new boolean[2 * R + 1][2 * C + 1]; // true = 선분
		int T = Integer.parseInt(br.readLine());

		while (T-- > 0) {
			st = new StringTokenizer(br.readLine());
			int startR = Integer.parseInt(st.nextToken());
			int startC = Integer.parseInt(st.nextToken());
			int endR = Integer.parseInt(st.nextToken());
			int endC = Integer.parseInt(st.nextToken());

			if (startR == endR) {
				int minC = Math.min(startC, endC);
				int maxC = Math.max(startC, endC);

				for (int c = minC * 2; c <= maxC * 2; c++) {
					board[startR * 2][c] = true;
				}
			} else if (startC == endC) {
				int minR = Math.min(startR, endR);
				int maxR = Math.max(startR, endR);

				for (int r = minR * 2; r <= maxR * 2; r++) {
					board[r][startC * 2] = true;
				}
			}
		}

		boolean[][] visited = new boolean[2 * R + 1][2 * C + 1];
		int maxSize = 0;
		int minSize = R * C;

		for (int r = 0; r <= R * 2; r++) {
			for (int c = 0; c <= C * 2; c++) {
				if (!visited[r][c] && !board[r][c]) {
					visited[r][c] = true;
					int size = 0;
					Queue<Pos> que = new LinkedList<>();
					int[] dirR = { -1, 1, 0, 0 };
					int[] dirC = { 0, 0, -1, 1 };
					que.add(new Pos(r, c));

					while (!que.isEmpty()) {
						Pos cur = que.remove();

						if (cur.row % 2 == 1 && cur.col % 2 == 1) {
							size++;
						}

						for (int d = 0; d < 4; d++) {
							int row = cur.row + dirR[d];
							int col = cur.col + dirC[d];

							if (row < 0 || row > R * 2 || col < 0 || col > C * 2) {
								continue;
							}

							if (visited[row][col] || board[row][col]) {
								continue;
							}

							visited[row][col] = true;
							que.add(new Pos(row, col));
						}
					}

					maxSize = Math.max(maxSize, size);
					minSize = Math.min(minSize, size);
				}
			}
		}

		System.out.println(maxSize);
		System.out.println(minSize);
		br.close();
	}
}