반응형
프로그래머스
DFS/BFS
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
MAX = 102
#테두리 그리기
graph = [[5]*MAX for _ in range(MAX)]
for r in rectangle:
x1, y1, x2, y2 = map(lambda x: x*2, r)
for i in range(x1, x2+1):
for j in range(y1, y2+1):
#내부일때 0으로 값 변경
if x1 < i < x2 and y1 < j < y2:
graph[i][j] = 0
#테두리이고 내부가 아닐 때 1로 값 변경
elif graph[i][j] != 0:
graph[i][j] = 1
#BFS로 최단거리 찾기
q = deque()
q.append([characterX * 2, characterY * 2])
visited = [[0]*MAX for _ in range(MAX)]
visited[characterX*2][characterY*2] = 1
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while q:
x, y = q.popleft()
if x == itemX * 2 and y == itemY * 2:
answer = (visited[x][y]-1) // 2
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if visited[nx][ny] == 0 and graph[nx][ny]==1:
q.append([nx, ny])
visited[nx][ny] = visited[x][y] + 1
return answer
반응형
'DS > Coding Test' 카테고리의 다른 글
[Python][백트래킹 Backtracking][DFS] 광물캐기 (0) | 2023.05.19 |
---|---|
[Python] 숫자 찾기 (0) | 2023.05.19 |
[Python][해시] 의상 (0) | 2023.05.19 |
[Python][Greedy][BFS] 조이스틱 (0) | 2023.05.19 |
[Python] 튜플 (0) | 2023.05.19 |