https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이 과정
여러개의 사각형이 주어질 때, 시작점에서 도착지점까지 사각형의 모서리만 타고 이동할 때의 최소 이동 횟수를 구하는 문제이다.
문제에서 주어진 예시와 같이 사각형의 내부는 방문할 수 없다.
입력값을 확인하면서 사각형의 모서리는 board값 1, 사각형 내부는 2, 내부와 모서리가 겹치는 경우는 내부가 우선해서 모서리 처리 안되게끔 board값을 처리하고 이동 가중치가 전부 1이니까 BFS로 board를 탐색하면서 최소 이동 거리를 구하면 답이 나올 것 같다. 하지만 이렇게 해결시 몇몇 테스트 케이스에서 오류가 발생한다.
위의 그림에서 (x, y) = (3, 5)인 지점을 보자. (4, 5)도 방문이 가능하지만 (3, 6)도 거리가 1만큼 떨어저 있고 사각형의 모서리에 해당하므로 방문이 가능하다고 판단해서 방문해버린다. 실제로는 (3, 6)을 방문하려면 (4, 5), (4, 6)을 먼저 방문해야 함에도 불구하고 말이다.
ㄷ자 모양의 모서리부분이 존재할 시, 바로 방문 불가능한 점을 방문이 가능하다고 처리하는 문제가 발생하는 것이다. 가장 간단한 해결방법은 좌표계를 2배 확대해서 보는 것이다. (1, 1)과 (1, 2) 사이에 2칸이 있다고 생각하는 것이다.
좌표계를 2배로 잡아서 보고 시작점, 도착지점 다 2배씩 해준 다음에 마지막에 구한 최소 이동 횟수도 2로 나눠주면 ㄷ자 모양의 모서리에서도 오류가 발생하지 않고 정상적으로 답을 구할 수 있다.
소스 코드
import collections
def solution(rectangle, characterX, characterY, itemX, itemY):
board = [[0 for _ in range(102)] for _ in range(102)]
for rec in rectangle:
a, b, c, d = rec
a *= 2; b *= 2; c *= 2; d *= 2
for y in range(b, d+1):
for x in range(a, c+1):
if board[y][x] == 2:
continue
if y == b or y == d or x == a or x == c:
board[y][x] = 1
else:
board[y][x] = 2
def bfs(start_y, start_x):
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
discovered = [[False for _ in range(102)] for _ in range(102)]
Q = collections.deque()
Q.append([start_y, start_x, 0])
discovered[start_y][start_x] = True
while Q:
cur_y, cur_x, dist = Q.popleft()
if cur_y == itemY*2 and cur_x == itemX*2:
return dist // 2
for i in range(4):
ny = cur_y + dy[i]
nx = cur_x + dx[i]
if 1 <= ny <= 100 and 1 <= nx <= 100 and board[ny][nx] == 1 and not discovered[ny][nx]:
Q.append([ny, nx, dist+1])
discovered[ny][nx] = True
answer = bfs(characterY*2, characterX*2)
return answer
'알고리즘 문제 풀이 > 프로그래머스' 카테고리의 다른 글
프로그래머스 - 여행경로 [파이썬] (0) | 2022.10.02 |
---|---|
프로그래머스 - 단어 변환 [파이썬] (0) | 2022.10.02 |
프로그래머스 - 게임 맵 최단거리 [파이썬] (1) | 2022.09.30 |
프로그래머스 - 조이스틱 [파이썬] (0) | 2022.09.30 |
프로그래머스 - 구명보트 [파이썬] (0) | 2022.09.27 |