[SWEA] 등산로 조성 (모의 SW 역량 테스트) / python

1. 문제 설명

등산로를 조성하려고 한다.
등산로를 만들기 위한 부지는 N * N 크기를 가지고 있으며, 이곳에 최대한 긴 등산로를 만들 계획이다.

 

등산로를 만드는 규칙은 다음과 같다.

① 등산로는 가장 높은 봉우리에서 시작해야 한다.

② 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.

즉, 높이가 같은 곳 혹은 낮은 지형이나, 대각선 방향의 연결은 불가능하다.

등산로를 조성하려나, 대각선 방향의 연결은 불가능하다.

③ 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
N * N 크기의 지도가 주어지고, 최대 공사 가능 깊이 K가 주어진다.
이때 만들 수 있는 가장 긴 등산로를 찾아 그 길이를 출력하는 프로그램을 작성하라.

 

 

[제약 사항]

1. 시간 제한 : 최대 51개 테스트 케이스를 모두 통과하는 데 C/C++/Java 모두 3초
2. 지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
3. 최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
4. 지도에 나타나는 지형의 높이는 1 이상 20 이하의 정수이다.
5. 지도에서 가장 높은 봉우리는 최대 5개이다.
6. 지형은 정수 단위로만 깎을 수 있다.
7. 필요한 경우 지형을 깎아 높이를 1보다 작게 만드는 것도 가능하다.

 

[입력]

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 지도의 한 변의 길이 N, 최대 공사 가능 깊이 K가 차례로 주어진다.

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

 

[출력]

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

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

출력해야 할 정답은 만들 수 있는 가장 긴 등산로의 길이이다.

 

2. 풀이 전 계획과 생각

• grid_size → 지도 한 변의 길이, depth→ 최대 공사 가능 깊이
• grid → 지도, 2차원 배열

 

• 구하고자 하는 바 ⇒ 만들 수 있는 가장 긴 등산로
• 조건
  • N ≤ 8, K ≤ 5
  • High → Low 등산로 연결 가능
  • 가장 높은 봉우리는 최대 5개
  • 한 지형을 K 깊이 만큼 깎을 수 있음
  • 등산로의 시작은 가장 높은 봉우리
  • 지형을 1보다 작게 만들 수 있음
• 패턴
  1. 시작 봉우리가 최대 5개이므로 이 지점부터 모든 경우를 탐색한다.
     • 경로의 특징이 있음으로 DFS 탐색을 한다.
  2. 만약 자기보다 높이가 높거나 같은 봉우리를 만났을 경우, 아직 등산로를 한번도 변경한 적이 없다면 해당 지형을 깎는다.
  3. 등산로의 최대 길이는 21 까지 나올 수 있다.

 

3. 풀이

def init():
    grid_size, depth = tuple(map(int, input().split()))
    grid = [ list(map(int, input().split())) for _ in range(grid_size) ]
    visited = [[False] * grid_size for _ in range(grid_size)]

    return grid_size, depth, grid, visited

def get_max_value():
    result = 1
    for y in range(grid_size):
        for x in range(grid_size):
            result = max(grid[y][x], result)
    return result

def get_start_pos():
    global max_value
    result = []

    for y in range(grid_size):
        for x in range(grid_size):
            if grid[y][x] == max_value:
                result.append((y, x))
    return result

def in_range(y, x):
    return 0 <= y < grid_size and 0 <= x < grid_size

def can_go(y, x, height):
    return in_range(y, x) and grid[y][x] < height

def dfs(current_pos, count, is_cut):
    # 2. 만약 자기보다 높이가 높거나 같은 봉우리를 만났을 경우, 
		# 아직 등산로를 한번도 변경한 적이 없다면 해당 지형을 깎는다.
    global visited
    dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]
    y, x = current_pos

    for dy, dx in zip(dys, dxs):
        next_y, next_x = y + dy, x + dx
        next_pos = (next_y, next_x)
        if in_range(next_y, next_x) and not visited[next_y][next_x]:
            # 내리막길인 경우
            if grid[y][x] > grid[next_y][next_x]:
                visited[next_y][next_x] = True
                dfs(next_pos, count + 1, is_cut)
                visited[next_y][next_x] = False
            # 내리막길이 아닌 경우
            else:
                if is_cut:
                    return count
                else:
                    is_cut = True
                    grid[y][x] -= depth
                    visited[next_y][next_x] = True
                    dfs(next_pos, count + 1, is_cut)
                    visited[next_y][next_x] = False

def solve():
    global start_pos, visited
    result = 0

    # 1. 시작 봉우리가 최대 5개이므로 이 지점부터 모든 경우를 탐색한다.
    for one_start_pos in start_pos:
        visited = [ [False] * grid_size for _ in range(grid_size) ]
        y, x = one_start_pos
        visited[y][x] = True
        result = max(result, dfs(one_start_pos, 0, False))

    return result

for test_case in range(1, int(input()) + 1):
    grid_size, depth, grid, visited = init()
    visited = [ [False] * grid_size for _ in range(grid_size) ]
    max_value = get_max_value()
    start_pos = get_start_pos()

    answer = solve()
    print(f'#{test_case} {answer}')

문제점

• dfs에서 return 하지 않는 경우가 발생한다.
  ⇒ 다른 경우를 체크해주기 위해서, 방문과 공사처리도 원상복귀 해주어야 한다.
  ⇒ 시작점도 경로에 포함해주어야 한다.
• 한 가지수에서 동시에 여러가지 수가 뻗어나가고 전역변수를 동시에 사용해주기 때문이다.
  ⇒ 이를 방지해주기 위해 return 대신 전역변수의 answer를 갱신하자.

 

4. 2차 풀이

def init():
    grid_size, depth = tuple(map(int, input().split()))
    grid = [ list(map(int, input().split())) for _ in range(grid_size) ]
    visited = [[False] * grid_size for _ in range(grid_size)]

    return grid_size, depth, grid, visited

def get_max_value():
    result = 1
    for y in range(grid_size):
        for x in range(grid_size):
            result = max(grid[y][x], result)
    return result

def get_start_pos():
    global max_value
    result = []

    for y in range(grid_size):
        for x in range(grid_size):
            if grid[y][x] == max_value:
                result.append((y, x))
    return result

def in_range(y, x):
    return 0 <= y < grid_size and 0 <= x < grid_size

def can_go(y, x, height):
    return in_range(y, x) and grid[y][x] < height

def dfs(current_pos, count, is_cut):
    # 2. 만약 자기보다 높이가 높거나 같은 봉우리를 만났을 경우, 
		# 아직 등산로를 한번도 변경한 적이 없다면 해당 지형을 깎는다.
    global visited, answer
    if answer < count:
        answer = count

    dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]
    y, x = current_pos

    for dy, dx in zip(dys, dxs):
        next_y, next_x = y + dy, x + dx
        next_pos = (next_y, next_x)

        if in_range(next_y, next_x) and not visited[next_y][next_x]:
            # 내리막길인 경우
            if grid[y][x] > grid[next_y][next_x]:
                visited[next_y][next_x] = True
                dfs(next_pos, count + 1, is_cut)
                visited[next_y][next_x] = False

            # 내리막길이 아닌 경우 및 아직 공사를 안 했다면,
            elif grid[y][x] <= grid[next_y][next_x] and not is_cut:
                # 공사하기
                is_cut = True
                grid[next_y][next_x] -= depth

                if grid[y][x] > grid[next_y][next_x]:
                    visited[next_y][next_x] = True
                    dfs(next_pos, count + 1, is_cut)
                    visited[next_y][next_x] = False

                # 공사 취소하기 (다른 경우를 체크해주기 위해)
                is_cut = False
                grid[next_y][next_x] += depth

def solve():
    global start_pos, visited

    # 1. 시작 봉우리가 최대 5개이므로 이 지점부터 모든 경우를 탐색한다.
    for one_start_pos in start_pos:
        visited = [ [False] * grid_size for _ in range(grid_size) ]
        y, x = one_start_pos
        visited[y][x] = True
        dfs(one_start_pos, 1, False)

for test_case in range(1, int(input()) + 1):
    grid_size, depth, grid, visited = init()
    visited = [ [False] * grid_size for _ in range(grid_size) ]
    max_value = get_max_value()
    start_pos = get_start_pos()

    answer = 0
    solve()
    print(f'#{test_case} {answer}')

문제점

• 테스트 케이스 51개중 49개만 맞췄다.
  ⇒1부터 K까지 깎았어야 했는데 계속 K 깊이로만 깎았다.
• 최대 K깊이만큼 지형을 깎을 수 있다. 😛

 

5. 3차 풀이

def init():
    grid_size, depth = tuple(map(int, input().split()))
    grid = [ list(map(int, input().split())) for _ in range(grid_size) ]
    visited = [[False] * grid_size for _ in range(grid_size)]

    return grid_size, depth, grid, visited

def get_max_value():
    result = 1
    for y in range(grid_size):
        for x in range(grid_size):
            result = max(grid[y][x], result)
    return result

def get_start_pos():
    global max_value
    result = []

    for y in range(grid_size):
        for x in range(grid_size):
            if grid[y][x] == max_value:
                result.append((y, x))
    return result

def in_range(y, x):
    return 0 <= y < grid_size and 0 <= x < grid_size

def can_go(y, x, height):
    return in_range(y, x) and grid[y][x] < height

def dfs(current_pos, count, is_cut):
    # 2. 만약 자기보다 높이가 높거나 같은 봉우리를 만났을 경우, 
	  # 아직 등산로를 한번도 변경한 적이 없다면 해당 지형을 깎는다.
    global visited, answer
    if answer < count:
        answer = count

    dys, dxs = [-1, 1, 0, 0], [0, 0, -1, 1]
    y, x = current_pos

    for dy, dx in zip(dys, dxs):
        next_y, next_x = y + dy, x + dx
        next_pos = (next_y, next_x)

        if in_range(next_y, next_x) and not visited[next_y][next_x]:
            # 내리막길인 경우
            if grid[y][x] > grid[next_y][next_x]:
                visited[next_y][next_x] = True
                dfs(next_pos, count + 1, is_cut)
                visited[next_y][next_x] = False

            # 내리막길이 아닌 경우 및 아직 공사를 안 했다면,
            elif grid[y][x] <= grid[next_y][next_x] and not is_cut:
                for current_depth in range(1, depth + 1):
                    # 공사하기
                    is_cut = True
                    grid[next_y][next_x] -= current_depth

                    if grid[y][x] > grid[next_y][next_x]:
                        visited[next_y][next_x] = True
                        dfs(next_pos, count + 1, is_cut)
                        visited[next_y][next_x] = False

                    # 공사 취소하기 (다른 경우를 체크해주기 위해)
                    is_cut = False
                    grid[next_y][next_x] += current_depth

def solve():
    global start_pos, visited

    # 1. 시작 봉우리가 최대 5개이므로 이 지점부터 모든 경우를 탐색한다.
    for one_start_pos in start_pos:
        visited = [ [False] * grid_size for _ in range(grid_size) ]
        y, x = one_start_pos
        visited[y][x] = True
        dfs(one_start_pos, 1, False)

for test_case in range(1, int(input()) + 1):
    grid_size, depth, grid, visited = init()
    visited = [ [False] * grid_size for _ in range(grid_size) ]
    max_value = get_max_value()
    start_pos = get_start_pos()

    answer = 0
    solve()
    print(f'#{test_case} {answer}')

 

6. 풀이 후 알게 된 개념과 소감

• 최대 K깊이만큼 지형을 깎을 수 있다.
  ⇒ 1부터 K까지 깎았어야 했는데 계속 K 깊이로만 깎았다.
• 다른 경우를 체크해주기 위해서, 방문과 공사처리도 원상복귀 해주어야 한다.
  ⇒ 한 가지수에서 동시에 여러가지 수가 뻗어나가고 전역변수를 동시에 사용해주기 때문이다.
• 시작점도 경로에 포함해주어야 한다.