[1949번] 등산로 조성

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. DFS

등산로 조성 문제는 N 제한이 작기 때문에 VISIT가 없는 완전 탐색으로 해결 할 수 있다.

BFS에 대한 해설은 아래 주석을 통해 달아두었고 이 문제는 DFS로 푸는 것이 정석적인 듯 하다.

(BFS로 풀기 위해서는 너무많은 for문이 필요)

소스 코드 : 

 
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,-1,0,1 };
int main() {
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
 
        int arr[10][10] = { 0, };
 
        int n, k;
        scanf("%d %d", &n, &k);
 
        int maxH = -1;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                scanf("%d", &arr[i][j]);
                maxH = max(maxH, arr[i][j]);
            }
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr[i][j] == maxH) { // 최고점을 만났을 때
                    
                    for (int a = 0; a < n; a++) { // a,b를 깎는다고 생각
                        for (int b = 0; b < n; b++) {
                            for (int t = 0; t <= k; t++) { // a,b를 0~k만큼 다깎아본다.
                                arr[a][b] -= t;
                                queue<pii> q;
                                q.push({ i,j });
 
                                int dist[10][10] = { 0, };
                                dist[i][j] = 1;
                                
                                while (!q.empty()) {
                                    int y = q.front().first;
                                    int x = q.front().second;
 
                                    q.pop();
 
                                    for (int w = 0; w < 4; w++) {
                                        int ny = y + dy[w];
                                        int nx = x + dx[w];
 
                                        if (0 <= ny && ny < n && 0 <= nx && nx < n && arr[y][x] > arr[ny][nx]) {
                                            dist[ny][nx] = dist[y][x] + 1;
                                            ans = max(ans, dist[ny][nx]); // 최장거리 갱신
                                            q.push({ ny,nx });
                                        }
                                    }
                                }
 
                                arr[a][b] += t;
                            }
                        }
                    }
 
                }
            }
        }
        printf("#%d %d\n", tc, ans);
    }
    return 0;
}