티어 및 알고리즘 분류
티어 – D4
알고리즘 분류
- DFS 구현
- 완전 탐색
문제
N 개의 방이 N×N형태로 늘어서 있다.
위에서 i번째 줄의 왼쪽에서 j번째 방에는 1이상 N² 이하의 수 A_i,j가 적혀 있으며, 이 숫자는 모든 방에 대해 서로 다르다.
당신이 어떤 방에 있다면, 상하좌우에 있는 다른 방으로 이동할 수 있다.
물론 이동하려는 방이 존재해야 하고, 이동하려는 방에 적힌 숫자가 현재 방에 적힌 숫자보다 정확히 1 더 커야 한다.
처음 어떤 수가 적힌 방에서 있어야 가장 많은 개수의 방을 이동할 수 있는지 구하는 프로그램을 작성하라.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (1 ≤ N ≤ 10³)가 주어진다.
다음 N개의 줄에는 i번째 줄에는 N개의 정수 A_i,1, … , A_i,N (1 ≤ A_i,j ≤ N²)이 공백 하나로 구분되어 주어진다.
A_i,j는 모두 서로 다른 수이다.
[출력]
각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 한 칸을 띄운 후, 처음에 출발해야 하는 방 번호와 최대 몇 개의 방을 이동할 수 있는지를 공백으로 구분하여 출력한다.
이동할 수 있는 방의 개수가 최대인 방이 여럿이라면 그 중에서 적힌 수가 가장 작은 것을 출력한다.
문제 접근 방식
1. 입력 및 초기화
입력으로 테스트 케이스 수와 N×N 크기의 방 정보를 받는다.
각 방에 적힌 숫자를 2차원 배열 map에 저장한다.
각 테스트 케이스마다 DFS 탐색을 위한 방문 배열 v를 초기화한다.
2. DFS 탐색 수행
모든 방을 시작점으로 DFS를 수행한다.
각 시작점에서 상하좌우로 이동 가능한지 검사한다.
이동 가능한 조건은 인접한 방의 숫자가 현재 방의 숫자보다 정확히 1 큰 경우이다.
방문 여부를 체크하며 경로의 길이를 누적한다.
3. 최대 이동 경로 갱신
DFS 수행 중 이동 횟수 cnt가 기존의 최대 이동 횟수 max보다 크거나 같으면 갱신한다.
동일한 이동 횟수일 경우, 시작점의 숫자가 더 작은 경우로 결과를 업데이트한다.
4. 결과 출력
모든 DFS 탐색 후, 최대 이동 가능 경로의 시작 방 번호와 이동 횟수를 출력한다.
구현 코드
import java.util.Arrays;
import java.util.Scanner;
class SSol1861{
static int value = 0;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int testCase = sc.nextInt();
for(int t = 1; t <= testCase; t++){
int n = sc.nextInt();
int[][] map = new int[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j< n; j++){
map[i][j] = sc.nextInt();
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int[] sp = new int[]{i,j};
boolean[][] v = new boolean[n][n];
v[sp[0]][sp[1]] = true;
dfs(map, 1, sp, Arrays.copyOf(sp, sp.length), n, v);
}
}
System.out.println("#"+t+" "+value + " " + max);
value = 0;
max = Integer.MIN_VALUE;
}
}
static void dfs(int[][] map, int cnt, int[] sp, int[] mp, int n, boolean[][] v){
int[] dx = {0,0,1,-1};
int[] dy = {1,-1,0,0};
for(int i = 0; i < 4; i++){
int xdx = mp[0] + dx[i];
int ydy = mp[1] + dy[i];
if(xdx >= 0 && xdx < n && ydy >= 0 && ydy < n && !v[xdx][ydy]){
if(Math.abs(map[xdx][ydy] - map[mp[0]][mp[1]]) == 1){
mp[0] = xdx;
mp[1] = ydy;
v[xdx][ydy] = true;
cnt++;
if(max <= cnt){
if(max == cnt){
if(value > map[sp[0]][sp[1]]){
value = map[sp[0]][sp[1]];
max = cnt;
}
}else{
value = map[sp[0]][sp[1]];
max = cnt;
}
}
dfs(map, cnt, sp, mp, n, v);
}
}
}
}
}마치며
문제의 조건을 만족하기 위해 DFS 탐색을 활용한 완전 탐색 방식을 선택하였다.
불필요한 중복 탐색을 피하기 위해 방문 배열을 사용하였다.
DFS를 통해 모든 경우의 수를 탐색하며 최적의 결과를 도출할 수 있었다.
문제 풀이 과정에서 깊이 우선 탐색의 중요성을 다시 한 번 깨달을 수 있었다.
다른 문제에서도 DFS를 활용할 수 있음을 확인할 수 있었다.