[SWEA] 1949 등산로 조성, 모의 SW 역량테스트, python

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

SW Expert Academy

 

for tc in range(1, int(input())+1):
    n, k = map(int, input().split())
    k_used_chk = False
    # 3<=n<=8, 1<=k<=5
    _map = []
    max_h = 0
    max_list = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        _map.append(tmp)
        for j in range(n):
            if tmp[j] > max_h:
                max_h = tmp[j]
                max_list = [(i, j)]
            elif tmp[j] == max_h:
                max_list.append((i, j))
    visited = [[0] * n for _ in range(n)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    max_val = 0


    def dfs(x, y, index=0):
        global k_used_chk, max_val
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny <n:
                if visited[nx][ny]: continue
                if k_used_chk and _map[nx][ny] >= _map[x][y]: continue
                if _map[nx][ny] >= _map[x][y]: # k를 사용하지 않은경우
                    for i in range(1, k + 1):
                        if _map[nx][ny] - i >= _map[x][y]: continue
                        k_used_chk = True
                        _map[nx][ny] -= i
                        visited[nx][ny] = 1
                        dfs(nx, ny, index + 1)
                        visited[nx][ny] = 0
                        _map[nx][ny] += i
                        k_used_chk = False
                else:#if _map[nx][ny] < _map[x][y]:
                    visited[nx][ny] = 1
                    dfs(nx,ny, index + 1)
                    visited[nx][ny] = 0
        tmp_val = index + 1
        if max_val < tmp_val:
            max_val = tmp_val

    for i in range(len(max_list)):
        visited[max_list[i][0]][max_list[i][1]] = 1
        dfs(max_list[i][0],max_list[i][1])
        visited[max_list[i][0]][max_list[i][1]] = 0

    print("#{} {}".format(tc, max_val))

조건이 더해진 DFS이다.

가장 높은 지점에서 시작하여 점점 낮은 지점으로 내려가는 등산로를 찾는데 가장 길게 만들어야한다.

이때 딱 한번 높이를 낮출수 있는데 이때 최대로 낮출수 있는 높이는 K이다.

DFS 함수 이전까지의 코드들은 입력들을 받고 변수들을 선언하는 코드이다.

- 최대의 높이(max_h), 최대 높이의 좌표(max_list), 방문체크를 위한 이차원 배열(visited), 공사를 했는지 체크(k_used_chk), delta, 최대 거리를 저장하는 변수

 

DFS 함수는 재귀로 구현을 했다. 사방을 탐색하면서 범위안에 있으면 방문한 점인지 체크한다.

조건에 위배되지 않으면 공사를 하지 않은경우와 공사를 한 경우로 나누어서 판단한다.

- 공사를 한 경우, 가려는 지점이 원래의 지점보다 크거나 같으면 갈수없으므로 빠져나온다.

-  공사를 하지 않은경우, 가려는 지점이 원래의 지점보다 크거나 같을때 범위를 1부터 K까지 주면서 현재 지점보다 낮아지는 경우 재귀함수를 호출한다.

가려는 지점이 원래 지점보다 작은경우에는 일반적인 DFS처럼 재귀함수를 호출한다.

 

DFS 함수 이후는 가장 높은 지점에서 한번씩 탐색을 해야하기 때문에 For문을 사용해서 모든지점을 탐색하였다.

그렇게 구했을때 max_val의 값이 등산로의 최대 길이가 된다.

---

처음 봤을때는 정말 어려웠는데 DFS를 재귀로 짜면서 조건을 몇개 걸어보니 얼추 구할수 있었다.

쉽진않지만 뚱땅거리면서 해보면 풀수는 있는것 같다.

아직 모의역량테스트는 세문제 더 풀어봐야하는데 막막하다...