SW Expert Academy 1949. [모의 SW 역량테스트] 등산로 조성 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

SW Expert Academy

나는 bfs로 풀었는데, 지금 생각해보니 dfs로 푸는 것이 메모리나 시간 측면에서 조금 더 적게 걸리고 풀 수 있을 것 같다. 다만 짜기 쉽게 하기 위해 나는 큐를 사용하여 풀었다. 가장 먼저 처음에 가장 큰 값을 찾기 위해 2중 for문을 2번이나 돌렸다. 이를 더 빠르게 하기 위해서는 n^2번 실행하고 각 값을 n으로 나눈 몫과 나머지 값으로 하여 체크한다면 시간 단축을 조금 더 할 수 있을 거라 생각한다. 이후 solution이라는 함수를 통해 문제를 해결하였는데, 먼저 주어진 맵에서 가장 큰 지점들을 큐에 넣어서, 각 값마다 한 지점을 깎았는지 여부를 flag를 통해 판단하고, 깎지 않았다면, 0부터 최대 깊이인 k까지 깎고, 큐에 넣고, 큐에 넣을 때마다 c를 증가시켜서 만약 4방위를 다 탐색하고도 한 번도 넣지 않았다면, 등산로 조성이 끝난 것이므로, 이때 지금까지 담아온 지점들의 길이가 현재 답보다 크다면, 최댓값을 갱신하도록 하였다. 해결한 코드는 아래와 같다.

from collections import deque


def solution(map1, maxpoints, k):
    answer = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    queue = deque()
    for i in maxpoints:
        queue.append([i[0], i[1], [[i[0], i[1]]], 0,map1[i[0]][i[1]]])
    while queue:
        x, y, sub, flag, value = queue.popleft()
        if flag == 0:
            for a in range(k + 1):
                c = 0
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if -1 < nx < n and -1 < ny < n and value > map1[nx][ny]-a and [nx, ny] not in sub:
                        c += 1
                        if a == 0:
                            queue.append([nx, ny, sub + [[nx, ny]], 0, map1[nx][ny]])
                        else:
                            queue.append([nx, ny, sub + [[nx, ny]], 1, map1[nx][ny]-a])
                if c == 0:
                    if len(sub) > answer:
                        answer = len(sub)

        else:
            c = 0
            for d in range(4):
                nx = x + dx[d]
                ny = y + dy[d]
                if -1 < nx < n and -1 < ny < n and value > map1[nx][ny] and [nx, ny] not in sub:
                    c += 1
                    queue.append([nx, ny, sub + [[nx, ny]], 1, map1[nx][ny]])
            if c == 0:
                if len(sub) > answer:
                    answer = len(sub)
    return answer


t = int(input())
for test in range(1, t + 1):
    n, k = map(int, input().split())
    maxv = 0
    maxpoints = []
    map1 = []
    for _ in range(n):
        s = list(map(int, input().split()))
        for i in range(n):
            if s[i] > maxv:
                maxv = s[i]
        map1.append(s)
    for i in range(n):
        for j in range(n):
            if map1[i][j] == maxv:
                maxpoints.append([i, j])
    ans = solution(map1, maxpoints, k)
    print('#{} {}'.format(test,ans))