[SWEA] 1861. 정사각형 방 (d4)

문제

---

N^2개의 방이 N×N형태로 늘어서 있다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N^2 이하의 수 Ai,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.

당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.

물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.

처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 103)이 주어진다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai, 1, … , Ai, N (1 ≤ Ai, j ≤ N2) 이 공백 하나로 구분되어 주어진다.

Ai, j는 모두 서로 다른 수이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.

이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.

[예제 풀이]

첫 번째 테스트 케이스는 1 또는 3이 적힌 곳에 있어야 한다.

두 번째 테스트 케이스는 3 또는 6이 적힌 곳에 있어야 한다.

입력

2
2
1 2
3 4
3
9 3 4
6 1 5
7 8 2

출력

#1 1 2
#2 3 3

풀이

---

문제 유형 : BFS

코드

---

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

public class Solution {
	
	static int N;
	static int[] ans;
	static int[][] room;
	static boolean[][] isVisited;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			
			room = new int[N][N];
			
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for(int j=0; j<N; j++) {
					room[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			ans = new int[2];	// [0] : 방 번호, [1] : 칸의 갯수
			isVisited = new boolean[N][N];
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(!isVisited[i][j]) {
						bfs(i, j);
					}
				}
			}
			
			sb.append("#").append(tc).append(" ").append(ans[0]).append(" ").append(ans[1]).append("\n");
		}
		
		System.out.println(sb.toString());
		br.close();
	}
	
	static int[] di = {-1, 0, 1, 0};
	static int[] dj = {0, 1, 0, -1};
	
	static void bfs(int u, int v) {
		isVisited[u][v] = true;
		int minNo = room[u][v];
		
		Queue<int[]> que = new LinkedList<int[]>();
		que.offer(new int[] {u, v});
		
		int cnt=1;
		
		while(!que.isEmpty()) {
			int[] cur = que.poll();
			
			for(int k=0; k<4; k++) {
				int ni = cur[0] + di[k];
				int nj = cur[1] + dj[k];
				
				if(ni<0 || ni>=N || nj<0 || nj>=N || isVisited[ni][nj]) continue;
				
				if(Math.abs(room[cur[0]][cur[1]] - room[ni][nj])==1) {
					cnt++;
					isVisited[ni][nj] = true;
					que.offer(new int[] {ni, nj});
					
					if(room[ni][nj] < minNo) minNo = room[ni][nj];
				}
			}
		}
		
		if(ans[1] < cnt) {
			ans[1] = cnt;
			ans[0] = minNo;
		}
		if(cnt == ans[1]) {
			ans[0] = ans[0] > minNo ? minNo : ans[0];
		}
	}

}