[SWEA] 정사각형 방

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

재귀를 사용해 풀었다.

 

rooms[][]에는 방 번호를, visitNum[][]에는 해당 위치의 방에서 방문할 수 있는 방의 개수를 저장한다.

처음에 visitNum[][]을 -1로 초기화하고, visitNum을 사용해 해당 방에서 방문할 수 있는 방의 개수를 세본 적이 있는지 확인한다.

 

이중 for문을 사용해 rooms에 접근해서, visitNum[i][j]가 -1이라면 getMoveNum(i, j) 함수를 호출하고, 리턴한 값을 visitNum[i][j]에 넣는다.

 

getMoveNum(i, j) 함수는 (i, j) 위치에서 몇 개의 방에 방문할 수 있는지를 return하는 함수이다.

(i, j)와 dx, dy 배열을 사용해 인접한 곳에 방문가능한 방이 있는지 먼저 확인한다.

-> rooms[i + dx[dir]][j + dy[dir]] = rooms[i][j] + 1이라면, 이동 가능

-> 이동 가능하다면, 재귀를 사용해 getMoveNum(i + dx[dir], j + dy[dir]) 값을 nextVisitNum에 받아오고, nextVisitNum + 1을 리턴한다. (getMoveNum 함수는 현재 위치에서 몇 개의 방에 방문할 수 있는지 return 하는 함수이므로!)

-> 이동이 불가능하다면, 현재 위치의 방만 방문할 수 있다는 뜻이므로, 1을 리턴한다!

 

코드

package swea;

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

// 정사각형 방 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE&problemTitle=%EC%A0%95%EC%82%AC%EA%B0%81%ED%98%95&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

public class SWEA_1861 {
	
	private static int N;
	private static int[][] rooms;
	private static int[][] visitNum;
	private static int[] dx = { 1, -1, 0, 0 };
	private static int[] dy = { 0, 0, 1, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T;
		
		T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			// input
			N = Integer.parseInt(br.readLine());
			rooms = new int[N][N];
			visitNum = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				
				for (int j = 0; j < N; j++) {
					rooms[i][j] = Integer.parseInt(st.nextToken());
					visitNum[i][j] = -1; // (i, j) 위치에서 이동해봤는지 확인하기 위해 -1로 초기화
				}
			}
			
			// solve
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (visitNum[i][j] == -1) { // moveNum[i][j]가 -1이라면, getMoveNum을 해준다.
						visitNum[i][j] = getMoveNum(i, j);
					}
				}
			}
			
			// 최대로 이동가능한 방 찾기
			int maxRoomI = 0;
			int maxRoomJ = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (visitNum[maxRoomI][maxRoomJ] < visitNum[i][j]) {
						maxRoomI = i;
						maxRoomJ = j;
					}
					// 최대인 방이 여러개일 경우, 적힌 수가 가장 작은 것을 출력한다.
					if ((visitNum[maxRoomI][maxRoomJ] == visitNum[i][j]) && (rooms[maxRoomI][maxRoomJ] > rooms[i][j])) {
						maxRoomI = i;
						maxRoomJ = j;
					}
				}
			}
			
			bw.write("#" + tc + " ");
			bw.write(rooms[maxRoomI][maxRoomJ] + " " + visitNum[maxRoomI][maxRoomJ]);
			bw.newLine();
		}
		
		bw.flush();
		bw.close();
	}
	
	private static int getMoveNum(int i, int j) {
		// 이동할 수 있는지 검사
		for (int dir = 0; dir < 4; dir++) {
			int nextI = i + dx[dir];
			int nextJ = j + dy[dir];
			
			if (nextI < 0 || nextI >= N || nextJ < 0 || nextJ >= N)
				continue;
			
			// 이동할 수 있는 경우
			if (rooms[nextI][nextJ] == rooms[i][j] + 1) {
				 // 이동할 방(nextI, nextJ)에서 이동할 수 있는 방들의 수 + 1이 현재 방에서 이동할 수 있는 수이다.
				int nextVisitNum = getMoveNum(nextI, nextJ);
				return nextVisitNum + 1;
			}
		}
		
		// 이동할 수 없는 경우, 현재 방만 방문할 수 있으므로 move[i][j]를 1로 바꾸고, return한다.
		visitNum[i][j] = 1;
		return visitNum[i][j];
	}

}