1861. 정사각형 방 - 자바(JAVA)

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc 

SW Expert Academy

 

문제 해석

N^2의 방이 NxN형태로 존재합니다.

위에서 i번째 줄의 왼쪽에서 j번째 방에는 1 이상 N^2 이하의 수 A(i, j)가 적혀 있습니다.

어떤 방에 있을때, 상하좌우에 있는 다른 방으로 이동할 수 있습니다.

이동하려는 방이 존재해야 하며, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 합니다.

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

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

 

입력

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

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N이 주어집니다.

다음 N개의 줄에는 i번째 줄에는 N개의 정수 Ai ~ Aj 가 공백하나로 구분되어 주어집니다.

 

제약조건

(1 ≤ N ≤ 10^3)

출력

각 테스트 케이스마다 '#x' (x는 테스트케이스 번호를 의미하며 1부터 시작합니다)를 출력하고, 한 칸을 띄운 후 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력합니다.

 

 

문제 풀이전 설계

문제를 처음보고 BFS 풀이를 생각했습니다.

N의 크기가 1000이하이기 때문에 시간 복잡도도 만족할 것으로 예상했습니다.

최소 거리를 찾는 것이 아닌 최대 거리를 찾아야 하므로 DFS를 사용하면 쉽게 풀릴 것 같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution_1861_정사각형방 {
	static int roomArray[][];
	static final int DIRECTION = 4;
	static int dy[] = { -1, 1, 0, 0 };
	static int dx[] = { 0, 0,- 1, 1 };
	static int N;
	static int maxMoveCount;
	static int startRoom;
	static List<Integer> tempRoom = new ArrayList<Integer>();

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= testCase; tc++) {
			maxMoveCount =1;
			startRoom = 0;
			N = Integer.parseInt(br.readLine());
			roomArray = new int[N][N];			
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					roomArray[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					tempRoom.add(roomArray[i][j]);
					DFS(1, i, j);
					tempRoom.clear();
				}
			}
			sb.append("#" + tc + " " + startRoom + " " + maxMoveCount + "\n");
		}
		System.out.println(sb.toString());
	}

	static void DFS(int cnt, int i, int j) {			
		int temp = tempRoom.get(0);
		if (cnt == maxMoveCount) {
			startRoom = startRoom < temp ? startRoom : temp;
		}
		if (cnt > maxMoveCount) {
			maxMoveCount = cnt;
			startRoom = temp;
		}

		// 4방탐색
		for (int k = 0; k < DIRECTION; k++) {
			int tempY = i + dy[k];
			int tempX = j + dx[k];
			if (tempY < 0 || tempX < 0 || tempY > N - 1 || tempX > N - 1) {
				continue;
			}
			if(roomArray[tempY][tempX] - roomArray[i][j] != 1) {
				continue;
			}
			tempRoom.add(roomArray[tempY][tempX]);
			DFS(cnt + 1, tempY, tempX);
		}
	}

}