SWEA 1861 - 정사각형 방

Java

1861 번 - 정사각형 방

문제

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

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

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

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

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

접근 방법

전형적인 DFS와 BFS 응용 문제이다. 두 알고리즘을 공부하기 위해 각각 구현하여 사용해 보았다.
(0,0)에서 부터 시작하여 (n-1, n-1)까지 시작점을 각각 DFS와 BFS에 인자로 주며 호출한다.
DFS와 BFS가 끝나면 각 시작점에서 출발하여 얻은 결과 값들이 있으며, 이 결과 값이 기존 결과 값보다 더 크면, 갱신한다.
문제 조건에서 결과 값이 같으면, 시작 방 중 제일 작은 값을 출력하라 하였으므로
결과 값이 같다면 시작 방 값을 비교하여 더 작은 값으로 갱신한다.

구현

DFS와 BFS를 각각 구현하여 두개의 실행 결과 값을 비교한다.

코드

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

class Solution {
	static int arr[][], n;
	static int result = 0;
	static int smallest = 999999999;
	public static void main(String []args) throws Exception {  
		System.setIn(new FileInputStream("res/input.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	int tc = stoi(br.readLine());
    	
    	for(int idx = 1; idx <= tc; idx++) {
    		n = stoi(br.readLine());
    		arr = new int[n][n];
    		int big = 0;
    		int startRoom = 0;
    		smallest = 999999999;
    		for(int i = 0; i < n; i++) {
    			st = new StringTokenizer(br.readLine());
    			for(int j = 0; j < n; j++) {
    				arr[i][j] = stoi(st.nextToken());
    			}
    		}
    		
    		for(int i = 0; i < n; i++) {			// 시작점 부여
    			for(int j = 0; j < n; j++) {
    				result = 0;
    				DFS(i,j, arr[i][j] - 1, 0);		// DFS로 해결, 둘 중 하나의 알고리즘으로 풀어본다.
    				//BFS(i,j);						// BFS로 해결
    				if(big < result) {				// DFS/ BFS의 결과 크기 비교
    					startRoom = arr[i][j];
    					big = result;
    				}
    				else if(big == result && arr[i][j] < startRoom) {		// 같은 결과면 방 값이 더 작은 값으로 갱신
    					startRoom = arr[i][j];
    				}
    			}
    		}
    		System.out.println("#" + idx + " " + startRoom +  " " + big);
    	}
	}
	
	static void DFS(int y, int x, int lastN, int cnt) {
		// 만약 범위를 벗어나거나, 현재 위치가 1차이가 나지 않으면 갈 수 없으므로 바로 종료
		if(y < 0 || y >= n || x < 0 || x >= n || arr[y][x] != lastN + 1) {
			result = Math.max(result, cnt);
			return;
		}
		DFS(y - 1, x, arr[y][x], cnt + 1);		//상
		DFS(y + 1, x, arr[y][x], cnt + 1);		//하
		DFS(y, x - 1, arr[y][x], cnt + 1);		//좌
		DFS(y, x + 1, arr[y][x], cnt + 1);		//우
	}
	
	//상, 우, 좌, 하
	static int goy[] = { 0, 1, -1, 0 };
	static int gox[] = { -1, 0, 0, 1 };
	static void BFS(int y, int x) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.offer(new int[] {y,x});				// 시작점을 일단 queue에 넣는다.
		result++;
		int dy, dx, ty, tx;
		while(!q.isEmpty()) {					// queue가 비면 더 이상 이동하지 않으므로 종료
			int[] temp = q.poll();
			dy = temp[0];
			dx = temp[1];
			for(int i = 0; i < 4; i++) {		// 상하좌우 하나씩 방문한다.
				ty = dy + goy[i];				
				tx = dx + gox[i];
				// 만약 범위를 벗어나지 않고, 상하좌우 값 중 하나가 1의 차이어서 갈 수 있으면
				if(ty >= 0 && ty < n && tx >= 0 && tx < n && arr[ty][tx] == arr[dy][dx] + 1) {
					result++;					// 한칸 이동했으므로 증가
					q.offer(new int[] {ty,tx});	// 움직인 곳에서 다시 상하좌우를 방문하기 위해 queue에 넣는다.
				}
			}
		}
	}	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐⭐★★

후기

DFS와 BFS를 복습하는 문제 였다.

개선할 점

없