문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=1861&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&&
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution {
private static int cnt = 1;
private static int[][] directions = {
{ -1, 0 },
{ 1, 0 },
{ 0, -1 },
{ 0, 1 },
};
public static void main(String[] args) throws IOException {
StringBuilder sb = new StringBuilder();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
int problemNum = 1;
while (T-- > 0) {
int result = 0;
int resultIndex = Integer.MAX_VALUE;
int N = Integer.parseInt(reader.readLine());
int[][] matrix = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
for (int j = 1; j <= N; j++) {
matrix[i][j] = Integer.parseInt(tokenizer.nextToken());
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int temp = bfs(matrix, N, i, j);
if (temp > result) {
result = temp;
resultIndex = matrix[i][j];
} else if (temp == result) {
resultIndex = Math.min(resultIndex, matrix[i][j]);
}
}
}
sb.append("#").append(problemNum++).append(" ");
sb.append(resultIndex).append(" ").append(result).append("\n");
}
System.out.println(sb);
}
private static int bfs(int[][] matrix, int N, int i, int j) {
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] { i, j });
int count = 1;
while (!queue.isEmpty()) {
int[] current = queue.poll();
for (int k = 0; k < 4; k++) {
int dx = current[0] + directions[k][0];
int dy = current[1] + directions[k][1];
if (dx >= 1 && dx <= N && dy >= 1 && dy <= N) {
if (matrix[dx][dy] == matrix[current[0]][current[1]] + 1) {
queue.offer(new int[] { dx, dy });
count++;
}
}
}
}
return count;
}
private static void dfs(int[][] matrix, int N, int i, int j) {
if (!(i >= 1 && i <= N && j >= 1 && j <= N)) return;
for (int k = 0; k < 4; k++) {
int dx = i + directions[k][0];
int dy = j + directions[k][1];
if (dx >= 1 && dx <= N && dy >= 1 && dy <= N) {
if (matrix[dx][dy] == matrix[i][j] + 1) {
cnt++;
dfs(matrix, N, dx, dy);
}
}
}
}
}
- 탐색을 연습해보기 위해 DFS, BFS 두 가지 방법 모두를 사용해 보았다.
- 인덱스 처리에서 애먹었는데, 문제의 요구사항이 어려운 것은 아닌데 뭔가 쉽게 되지 않았다.
- DFS, BFS 모두 적용할 수 있었다.