✅[모의 SW 역량테스트] 등산로 조성

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq 

SW Expert Academy

 

#1. 설계 및 풀이

1. 최대 봉우리를 찾기

2. 최대 봉우리마다 최댓값 구하기

2-1) 최대 봉우리가 아닌 곳을 임의로 하나 정해서 0~k까지 깎기

2-2) 백트래킹 수행해서 최댓값을 갱신

3. 최댓값 출력

 

import copy
from collections import deque

def cut(board, i, j, h) :
    temp = copy.deepcopy(board)
    temp[i][j] -= h
    if temp[i][j] < 0 :
        return None
    return temp

def get_bongs(board) : # 최대 봉우리 찾기
    bongs = []
    max_val = 0
    for b in board:
        max_val = max(max_val, max(b))

    for i in range(n):
        for j in range(n):
            if board[i][j] == max_val:
                bongs.append([i, j])
    return bongs

def dfs(x, y, board, visited, cnt) :
    global answer
    for i in range(4) :
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n :
            if visited[nx][ny] == 0 and board[nx][ny] < board[x][y] :
                visited[nx][ny] = 1
                dfs(nx, ny, board, visited, cnt+1)
                visited[nx][ny] = 0
    answer = max(answer, cnt)


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
T = int(input())
for test_case in range(1, T + 1):
    answer = 0
    n, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    bongs = get_bongs(board)

    for x, y in bongs :
        for i in range(n) :
            for j in range(n) :
                for h in range(k+1) :
                    if x == i and y == j :
                        break
                    new_board = cut(board, i, j, h)
                    if new_board != None :
                        visited = [[0] * n for _ in range(n)]
                        visited[x][y] = 1
                        dfs_max = 0
                        dfs(x, y, new_board, visited, 1)

    print("#" + str(test_case), answer)

 

#2. 배운 점

 

# 테스트케이스 하나 틀린 풀이

import copy
from collections import deque

def cut(board, i, j, h) :
    temp = copy.deepcopy(board)
    temp[i][j] -= h
    if temp[i][j] < 0 :
        return None
    return temp

def get_bongs(board) : # 최대 봉우리 찾기
    bongs = []
    max_val = 0
    for b in board:
        max_val = max(max_val, max(b))

    for i in range(n):
        for j in range(n):
            if board[i][j] == max_val:
                bongs.append([i, j])
    return bongs

def dfs(x, y, board, visited, cnt) :
    global answer
    for i in range(4) :
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < n :
            if visited[nx][ny] == 0 and board[nx][ny] < board[x][y] :
                visited[nx][ny] = 1
                dfs(nx, ny, board, visited, cnt+1)
                visited[nx][ny] = 0
    answer = max(answer, cnt)


dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
T = int(input())
for test_case in range(1, T + 1):
    answer = 0
    n, k = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]

    for i in range(n) :
        for j in range(n) :
            for h in range(k+1) :
                new_board = cut(board, i, j, h)
                if new_board != None :
                    bongs = get_bongs(new_board)
                    for bong in bongs :
                        visited = [[0] * n for _ in range(n)]
                        visited[bong[0]][bong[1]] = 1
                        dfs_max = 0
                        dfs(bong[0], bong[1], new_board, visited, 1)

    print("#" + str(test_case), answer)

 

- 테스트케이스 중 하나가 틀려서 보니까 문제를 잘못이해했다.

 

"가장 높은 봉우리에서 시작해야한다."

이 말이 산을 깎고 높은 봉우리를 구하는 것이 아니라, 높은 봉우리를 제외한 산을 깎으라는 뜻이었다.

이것만 놓고 보면 헷갈릴 수도 있는데, 예제케이스를 설명하는 곳을 보면

"이 세곳에서 출발하는 가장 긴 등산로 중 하나"라고 주어져서 더 확실하게 알 수 있었다.

 

--> 문제를 정말 한줄 한줄 꼼꼼히 읽어야겠다.

 

- BFS/DFS와 백트래킹을 구분하지 못했다.

그래프 탐색이라 당연히 BFS/DFS를 생각해서 풀어야지 하고 생각하고 있었는데

설계하고 구현하고보니 그제서야 틀렸다는 걸 알 수 있었다........

 

BFS/DFS는 그저 연결된 노드들을 모두 탐색하는 방법이라면 (그 중 BFS는 최단거리 탐색에도 쓰이지만)

이 문제는 갈 수 있는 최대길이를 찾으라고 하는 문제였다.

이는 모든 경우를 탐색하는 백트래킹 알고리즘을 사용해야한다.