문제
https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.
만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
풀이
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
MAX = 102 # 두배로 늘리기 때문에 최대 102
# 테두리 그리기
field = [[5]* MAX for _ in range(MAX)] # 5는 맨 처음 땅
for rec in rectangle:
x1, y1, x2, y2 = map(lambda x:x*2, rec)
for i in range(x1, x2+1):
for j in range(y1, y2+1):
if x1<i<x2 and y1<j<y2: # 내부일 때
field[i][j] = 0
elif field[i][j] != 0: # 테두리 or 이미 내부가 아닐 때
field[i][j] = 1 # 테두리랑 내부랑 겹치면 그건 내부
# 길찾기
q = deque()
q.append([characterX * 2, characterY * 2])
visited = [[0] * MAX for _ in range(MAX)]
visited[characterX * 2][characterY * 2] = 1
dx, dy = [-1, 1, 0, 0], [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 k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if visited[nx][ny] == 0 and field[nx][ny] == 1:
q.append([nx, ny])
visited[nx][ny] = visited[x][y] + 1
return answer

설명
알고리즘도 이해되지 않았다ㅠㅠ
1. 테두리 그리기
- 2차원 배열을 만들고
- 테두리는 1, 내부는 0 으로 표시
- 테두리와 내부가 겹칠 경우 0으로 표시
- 2배를 주고 테두리를 잡았다: 2배를 하지 않으면 길이 아니더라도 1칸 차이가 날 수 있기 때문에 경로가 되어버린다.
※ 좌표가 인접한 경우 탐색을 제대로 하기 어렵다. 따라서, 좌표를 2배로 확대해서, 테두리 사이의 공간을 마련해 주어야 한다.

'Coding Test > Python' 카테고리의 다른 글
| [백준] ABCDE (1) | 2023.09.03 |
|---|---|
| [프로그래머스] 여행경로 (lv.3) (0) | 2023.08.28 |
| [프로그래머스] 단어 변환 (lv.3) (0) | 2023.08.16 |
| [프로그래머스] 게임 맵 최단거리 (0) | 2023.08.15 |
| [프로그래머스] 네트워크 (lv.3) (0) | 2023.08.11 |