[SWEA] 1861. 정사각형 방

문제

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

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

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

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

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

 

풀이방법

DFS(깊이 우선 탐색)로 모든 경로를 찾는다. 

 

A[i][j] = x일 때, 상하좌우의 원소로 방문할 수 있는 경우는, 방문하려는 원소의 값이 x + 1이면서 방문한 적이 없어야한다.

 

위의 조건을 만족하는 모든 경로 중 경로의 길이가 가장 긴 경우를 찾되, 길이가 같을 경우, 시작 원소가 가장 작을 값을 출력한다.

 

소스코드

package samsung;

import java.util.*;

public class s_1861 {
	static int[][] a;
	static int n;
	static int[][] visit;
	static int idx;
	static int max;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	public static void dfs(int start, int depth, int x, int y) {
		visit[x][y] = 1;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
				if(a[nx][ny] == (a[x][y] + 1) && visit[nx][ny] == 0)
					dfs(start, depth + 1, nx, ny);
			}
		}
		if(depth > max) {
			max = depth;
			idx = start;
		}
		if(depth == max) {
			idx = Math.min(idx, start);
		}
		visit[x][y] = 0;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			a = new int[n][n];
			visit = new int[n][n];
			idx = 0;
			max = 0;
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					dfs(a[i][j], 1,  i, j);
				}
			}
			
			System.out.println("#" + t + " " + idx + " " + max);
		}
	}
}