[SWEA] #1861 - 정사각형 방

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

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

SW Expert Academy

 

💡 문제

---

[설명]

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

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

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

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

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

 

[제약 사항]

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

 

💡 아이디어

---

4방 탐색을 조금 응용하면 이 문제를 쉽게 해결할 수 있다.

우선 상, 하, 좌, 우를 탐색하면서 이동할 수 있는 방의 개수를 반환하는 함수를 만든다.

함수를 만들 때는 현재 적힌 숫자보다 1이 큰 방으로만 이동할 수 있기 때문에 이 조건을 추가해야 한다.

그 후 N^2개의 방의 첫 번째를 시작으로 마지막까지 함수를 실행하면 이동할 수 있는 최대 방의 개수를 구할 수 있다.

 

💡 소스코드

---

package SWEA;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class SWEA_P1861_정사각형_방 {
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1861_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			int N = Integer.parseInt(br.readLine());
			int MAX = 0;
			int start = 0;

			int[][] rooms = new int[N + 1][N + 1];

			for (int i = 1; i <= N; i++) {
				StringTokenizer sz = new StringTokenizer(br.readLine());
				for (int j = 1; j <= N; j++)
					rooms[i][j] = Integer.parseInt(sz.nextToken());
			}
			
			for (int i = 1; i <= N; i++) {
				for (int j = 1; j <= N; j++) {
					int move = solve(rooms, i, j);
					
					if(move > MAX) {
						MAX = move;
						start = rooms[i][j];
					}
					
					else if(move == MAX && rooms[i][j] < start)
						start = rooms[i][j];
				}					
			}
			
			
			System.out.print("#" + TC + " " + start + " " + (MAX + 1));
			System.out.println("");
		}
		br.close();
	}

	public static int solve(int[][] rooms, int i, int j) {
		int[] dx = { -1, 0, 1, 0 };
		int[] dy = { 0, 1, 0, -1 };
		boolean[][] visited = new boolean[rooms.length][rooms.length];

		Stack<Integer> X = new Stack<Integer>();
		Stack<Integer> Y = new Stack<Integer>();

		int curX = i;
		int curY = j;
		int cnt = 0;

		X.push(i);
		Y.push(j);
		visited[i][j] = true;

		while (true) {
			curX = X.pop();
			curY = Y.pop();
			visited[curX][curY] = true;

			for (int k = 0; k < 4; k++) {
				if (curX + dx[k] >= 1 && curX + dx[k] <= (rooms.length - 1) && curY + dy[k] >= 1
						&& curY + dy[k] <= (rooms.length - 1))
					if (rooms[curX + dx[k]][curY + dy[k]] - rooms[curX][curY] == 1
							&& visited[curX + dx[k]][curY + dy[k]] == false) {
						X.push(curX + dx[k]);
						Y.push(curY + dy[k]);
						cnt++;
					}
			}

			if (X.isEmpty() && Y.isEmpty())
				break;
		}

		return cnt;
	}
}

 

💡 결과

---

내가 작성한 코드는 조금 비효율적이다.

문제를 해결할 순 있지만, N이 커질수록 시간도 크게 증가하게 된다.

DFS를 재귀적으로 호출하여 완전 탐색을 수행하면 아마 시간이 확실히 줄어들 것 같아

다음에 한 번 다른 방법으로 문제를 풀어봐야겠다.