https://school.programmers.co.kr/learn/courses/30/lessons/62050
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제설명
N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.
이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.
각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.
제한사항
- land는 N x N크기인 2차원 배열입니다.
- land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
- land의 원소는 각 격자 칸의 높이를 나타냅니다.
- 격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
- height는 1 이상 10,000 이하인 자연수입니다.
문제 해결 방법
BFS를 활용해서 문제를 풀었다. 그런데 BFS를 할 때, 고려해줘야 하는게 있었다.
바로 사다리 설치비용이다. 문제에서 요구한대로 최소한의 사다리 설치 비용을 산출해내야 되기 때문에, 좌표에서 상, 하, 좌, 우 이동시 발생할 수 있는 사다리 설치 비용에 대해서 우선순위를 매겨야한다. 이때 heapq 우선순위 큐를 활용하여 문제를 해결했다.
코드 구현
BFS, heapq 자료구조를 이용해 풀이한 코드
import heapq
def solution(land, height):
answer = 0
# 좌표 움직임을 위한 배열
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
#시작 좌표
startX, startY = 0, 0
# 방문 여부 확인을 위한 배열
visited = [[False] * len(land) for _ in range(len(land[0]))]
heap = []
def bfs(stratX, startY):
answer = 0
heapq.heappush(heap, [0, startX, startY]) # 비용, startX, startY
while len(heap) != 0:
cost, x, y = heapq.heappop(heap)
#print('cost', cost)
if visited[y][x] == False:
visited[y][x] = True
answer += cost
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
continue
if abs(land[y][x]-land[ny][nx]) <= height:
newcost = 0
else:
newcost = abs(land[y][x]-land[ny][nx])
heapq.heappush(heap, [newcost, nx, ny])
return answer
answer = bfs(startX, startY)
#print(answer)
return answer
BFS구현 및 deque로 구현하려다가 실패한 코드
from collections import deque
def solution(land, height):
answer = 0
realAnswer = 0
# 좌표 움직임을 위한 배열
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
#시작 좌표
startX, startY = 0, 0
# 방문 여부 확인을 위한 배열
visited = [[False] * len(land) for _ in range(len(land[0]))]
check = [[10000] * len(land[0]) for _ in range(len(land))]
print(visited)
queue = deque()
def bfs(stratX, startY):
#시작하는 좌표를 큐에 넣고,
# 큐에 값이 있으면 큐에서 값을 꺼내어 방문 처리를 한다.
# 꺼낸 값에 인접한 값 중에서 방문하지 않은 좌표인지 확인한 후,
# 방문하지 않았으면 큐에 넣는다.
queue.append([startX, startY])
nx = 0
ny = 0
while len(queue) != 0:
x, y = queue.popleft()
visited[y][x] = True
print('')
print('x, y', x, y)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
print('i', i, 'nx, ny:', nx, ny)
# 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
print('?1')
continue
if visited[ny][nx] == True:
print(visited)
print('?2')
continue
print('nx, ny', nx, ny, 'x', 'y', x, y)
print(land[y][x], land[ny][nx])
if abs(land[y][x]-land[ny][nx]) <= height:
check[ny][nx] = abs(land[y][x]-land[ny][nx])
print('input', nx, ny)
queue.append([nx, ny])
# else:
# if check[ny][nx] > abs(land[y][x]-land[ny][nx]):
# check[ny][nx] = abs(land[y][x]-land[ny][nx])
# print('input', nx, ny)
# queue.append([nx, ny])
bfs(startX, startY)
check[0][0]=0
print('check', check)
return answer
시간/공간 복잡도
최악의 경우 O(N^2log(N^2))
최적화 및 개선 / 어려웠던 점
진짜 BFS에서 좌표 문제는 항상 헷갈리는 것 같다.
이 문제를 풀면서 깨달은 것은 이차원배열에서 x, y 좌표의 값을 구하고 싶으면
이차원배열명[y][x]
이렇게 호출해야 한다는 점이다.
그리고 heapq와 deque의 사용처에 대해서 분명히 알게됐다.
heapq는 deque보다 자료의 우선순위를 매겨야 할 때 사용하는 것이 적절하다.
반대로 자료의 우선순위를 매겨야할 때 deque를 사용하는 것은 적절치 않다.
'CodingTest > 문제 풀이 - Python' 카테고리의 다른 글
| [백준22232] 가희와 파일 탐색기 (1) | 2024.06.17 |
|---|---|
| [프로그래머스 lv2] 롤케이크 자르기 (0) | 2024.06.11 |
| [프로그래머스 lv2] 가장 큰 수.ver2 (0) | 2024.05.31 |
| [프로그래머스 lv2] 땅따먹기(DP) (1) | 2024.05.30 |
| [프로그래머스 lv2] k진수에서 소수 개수 구하기 (0) | 2024.05.28 |
