[SWEA]1949. 등산로 조성(Python) / DFS

SW Expert Academy에 있는 삼성 모의 SW 역량테스트 문제이다.

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

SW Expert Academy

45분 정도 소요

본 문제는 이미 여러번 풀어봤기 때문에 문제도 보지 않고 바로 코드를 쳐 나갔다.

같은 문제를 풀 때마다 매번 아이디어가 조금씩 다르고 보다 효율적인 자료구조, 알고리즘을 쓰기 위해 노력하고 있다.

 

로직은 간단하다.

맵에서 가장 높은 위치를 만날 때 방문표시 하고,

DFS를 사용해 함수 내에서

• 진입할 때마다 최대 길이를 갱신해준다.
• 다음 이동할 위치가 현재 위치보다 낮으면 정상적으로 방문처리하면서 거리를 저장한다. 
• 산을 깎을 수 있는 기회를 가지고 있고 다음 이동할 위치에서 K를 깎은 것이 현 위치보다 작다면 기회 사용한다.
  • 이 때, 이동할 위치의 깎기 전에 높이를 저장해놓고 재귀 풀려 나오면서 높이를 되돌려준다. 여기를 간과한 것이 실수 포인트,,
  • 이동할 위치를 1부터 K까지 검사하면서 다 깎기보다 현 높이보다 딱 1만큼만 낮게 만들어주면 충분하다.
• 재귀 풀려 나올 때는 방문처리한 것, 산을 깎았다면 높이를 되돌려놓는 작업이 필수적이다.

파이썬 코드는 다음과 같다.

 

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def dfs(r, c, chance):
    global MAX, visited
    MAX = max(MAX, visited[r][c])
    for d in range(4):
        nr = r + dr[d]
        nc = c + dc[d]
        if not (0 <= nr < N and 0 <= nc < N) or visited[nr][nc]:
            continue
        if A[r][c] > A[nr][nc]:
            visited[nr][nc] = visited[r][c] + 1
            dfs(nr, nc, chance)
            visited[nr][nc] = 0
        elif chance and A[nr][nc] - K < A[r][c]:
            temp = A[nr][nc]
            A[nr][nc] = A[r][c] - 1
            visited[nr][nc] = visited[r][c] + 1
            dfs(nr, nc, chance-1)
            visited[nr][nc] = 0
            A[nr][nc] = temp

# main
T = int(input())
for tc in range(T):
    N, K = map(int, input().split())
    A = []
    top = 0
    for i in range(N):
        A.append(list(map(int, input().split())))
        for j in range(N):
            if A[i][j] > top:
                top = A[i][j]
    MAX = 0
    visited = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if A[i][j] == top:
                visited[i][j] = 1
                dfs(i, j, 1)
                visited[i][j] = 0

    print("#{} {}".format(tc+1, MAX))

 

- 실행시간 : 249 ms / 메모리 : 62,812 kb

 

고찰 : 로직 제대로 설계하지 않고 바로 코드부터 치기 시작했다. 잔 실수의 원인이 된다.

        늘 제대로 설계하고 코드를 짜자. 알고리즘은 설계부터가 코딩의 시작이다.