[SWEA]#4014 [모의 SW 역량테스트] 활주로 건설

문제

#4014 [모의 SW 역량테스트] 활주로 건설

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T 가 주어지고,

그 다음 줄부터 T 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 크기인 N 과 경사로의 길이 X 가 주어진다.

다음 N 개의 줄에는 N * N 크기의 지형 정보가 주어진다.

출력

테스트 케이스 개수만큼 T 개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t" 로 시작하고 공백을 하나 둔 다음 정답을 출력한다. ( t 는 1 부터 시작하는 테스트 케이스의 번호이다. )

정답은 활주로를 건설할 수 있는 경우의 수이다.

예제 입력 1

10

6 2

3 3 3 2 1 1

3 3 3 2 2 1

3 3 3 3 3 2

2 2 3 2 2 2

2 2 3 2 2 2

2 2 2 2 2 2

6 4

3 2 2 2 1 2

3 2 2 2 1 2

3 3 3 3 2 2

3 3 3 3 2 2

3 2 2 2 2 2

3 2 2 2 2 2

…

예제 출력 1

#1 7

#2 4

#3 11

#4 11

#5 15

#6 4

#7 4

#8 1

#9 5

#10 8

풀이

이 문제는 DFS알고리즘을 이용해서 쉽게 풀 수 있는 문제였다. DFS 알고리즘을 정확히 이해하고 있다면 풀 수 있다. 이 문제는 백준의 경사로 문제와 비슷한 문제로 참고해보면 좋을 것 같다.

import java.io.InputStreamReader;
import java.io.BufferedReader;
 
class Solution
{
    static int[] dx = {1, 0};
    static int[] dy = {0, 1};
    static int[][] map;
    static int N;
    static int X;
    static int ans;
     
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
         
        for(int test_case = 1; test_case <= T; test_case++)
        {
            String[] input = br.readLine().split(" ");
            N = Integer.parseInt(input[0]);
            X = Integer.parseInt(input[1]);
            map = new int[N][N];
            ans = 0;
             
            for(int i=0; i<N; i++) {
                input = br.readLine().split(" ");
                for(int j=0; j<N; j++)
                    map[i][j] = Integer.parseInt(input[j]);
            }
             
            for(int i=0; i<N; i++)
                dfs(0, i, 0, 1, false);
             
            for(int i=0; i<N; i++)
                dfs(i, 0, 1, 1, false);
           
            System.out.println("#"+test_case+" "+ans);
        }
    }
     
    public static void dfs(int x, int y, int idx, int cnt, boolean flag) {
        int nx = x+dx[idx];
        int ny = y+dy[idx];
             
        if(nx==N || ny==N) {
            if(flag && cnt>=X || !flag) ans++;
            return;
        }
         
        if(map[x][y] == map[nx][ny])
            dfs(nx, ny, idx, cnt+1, flag);
         
        else {
            if(Math.abs(map[x][y] - map[nx][ny])>=2) return;
             
            if(map[x][y]<map[nx][ny] && !flag && cnt>=X)
                dfs(nx, ny, idx, 1, false);
             
            else if(map[x][y]<map[nx][ny] && flag && cnt>=2*X)
                dfs(nx, ny, idx, 1, false);
             
            else if(map[x][y]>map[nx][ny] && flag && cnt>=X)
                dfs(nx, ny, idx, 1, true);
             
            else if(map[x][y]>map[nx][ny] && !flag)
                dfs(nx, ny, idx, 1, true);
        }
    }
}