https://school.programmers.co.kr/learn/courses/30/lessons/87694?language=python3
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
오랜만에 알고리즘 문제를 풀어봤다. 깊이/너비 우선 탐색에 있는 아이템 줍기 문제로 알고리즘 고득점 kit에 있는 문제이다.
주어진 사각형들의 외곽선을 따라 아이템과 캐릭터의 최단길이를 구하는 문제이다. 처음 봤을 때 어떻게 풀어야 하지 싶었지만 차근차근 필요한 부분을 생각해 보았다.
💁🏻 외곽선 구하기
제일 먼저 그래프 탐색을 위한 외곽선을 구해야 하는데 어떻게 구해야 할까 생각해 봤는데 정말 단순하게 먼저 생각난 아이디어는
사각형마다 그래프에 0: 외부, 1: 내부, 2: 외곽선 이렇게 표시해서 다른 사각형을 표시할 때 이미 내부로 표시된 부분은 넘어가고 외곽선인 부분이 겹친다면 내부로 변경해 주어 외곽선을 표시하는 방식이었다.
위의 아이디어대로 코드로 구현해 봤다.
def check_rec_area(rectangle):
boundingBox = [-1,-1] # maxRtX, maxRtY
# 사각형들의 바운딩박스를 구함
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
boundingBox[0] = max(boundingBox[0], rtX)
boundingBox[1] = max(boundingBox[1], rtY)
width = boundingBox[0] + 1
height = boundingBox[1] + 1
graph = [[0] * width for i in range(height)]
# 사각형의 외각선과 내부 표시 (0: 외부, 1: 내부, 2: 외각선)
# 규칙 | 0: 1,2 변경가능/ 1: 변경 불가능/ 2: 1 변경가능
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
for j in range(height):
for i in range(width):
# 내부
if j > lbY and j <rtY and i>lbX and i<rtX:
if graph[j][i] == 0 or graph[j][i] == 2:
graph[j][i] = 1
# 외각선 가로
if j == lbY or j == rtY:
if i >= lbX and i <= rtX:
if graph[j][i] == 0:
graph[j][i] = 2
# 외각선 세로
if i == lbX or i == rtX:
if j >= lbY and j <= rtY:
if graph[j][i] == 0:
graph[j][i] = 2
for i in graph[::-1]:
print(i)
return graph
순간 뭔가 잘 못 나왔나 싶었지만 사각형을 그려보면 제대로 출력되고 있는 걸 볼 수 있다!
👨🏻💻 BFS로 최단거리 구하기
from collections import deque
def check_rec_area(rectangle):
boundingBox = [-1,-1] # maxRtX, maxRtY
# 사각형들의 바운딩박스를 구함
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
boundingBox[0] = max(boundingBox[0], rtX)
boundingBox[1] = max(boundingBox[1], rtY)
width = boundingBox[0] + 1
height = boundingBox[1] + 1
graph = [['∙'] * width for i in range(height)]
# 사각형의 외각선과 내부 표시 (0: 외부, 1: 내부, 2: 외각선)
# 규칙 | 0: 1,2 변경가능/ 1: 변경 불가능/ 2: 1 변경가능
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
for j in range(height):
for i in range(width):
# 내부
if j > lbY and j <rtY and i>lbX and i<rtX:
if graph[j][i] == '∙' or graph[j][i] == "◼︎":
graph[j][i] = "◻︎"
# 외각선 가로
if j == lbY or j == rtY:
if i >= lbX and i <= rtX:
if graph[j][i] == '∙':
graph[j][i] = "◼︎"
# 외각선 세로
if i == lbX or i == rtX:
if j >= lbY and j <= rtY:
if graph[j][i] == '∙':
graph[j][i] = "◼︎"
return [graph, width, height]
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
graph, w, h = check_rec_area(rectangle)
que = deque()
que.append([characterX, characterY, 0])
graph[characterY][characterX] = "◻︎"
print("start")
for g in graph[::-1]:
print(g)
print("")
while que:
popX, popY, count = que.popleft()
if popX == itemX and popY == itemY:
answer = count
break
for n in range(4):
nx = popX + dx[n]
ny = popY + dy[n]
if w > nx >= 0 and h > ny >= 0 and graph[ny][nx] == "◼︎":
que.append([nx, ny, count + 1])
graph[ny][nx] = "◻︎"
for g in graph[::-1]:
print(g)
print(f"(count: {count + 1} x,y: {popX}, {popY})")
return answer
이렇게 풀었는데 3문제는 맞았지만 2문제에서 예외가 생겼다. 확인해보니 외곽선이 바로 붙어있는 경우에는 건너뛰어지는 문제가 있었다.
진짜 1시간 동안 아무리 생각해봐도 답이 없어서 무식하지만 제일 처음 생각이 들었던 그냥 외곽선이 붙어있지 않게 x2배 해주어 짝수 층만 카운팅하는 방식으로 해결했다. ㅎㅎ
더 좋은 방법이 있다면 알려주세요~~~ 저는 그냥 이렇게 풀고 자러갈게요...
처음에는 0, 1, 2로 하다가 디버깅하는데 눈이 아파서 특수문자로 변경했더니 잘보인다 (카운팅은 ⚀ 이렇게 표시했어요)
from collections import deque
def check_rec_area(rectangle):
boundingBox = [-1,-1] # maxRtX, maxRtY
# 사각형들의 바운딩박스를 구함
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
boundingBox[0] = max(boundingBox[0], rtX)
boundingBox[1] = max(boundingBox[1], rtY)
width = (boundingBox[0] + 1) * 2
height = (boundingBox[1] + 1) * 2
graph = [['∙'] * width for i in range(height)]
# 사각형의 외각선과 내부 표시 (0: 외부, 1: 내부, 2: 외각선)
# 규칙 | 0: 1,2 변경가능/ 1: 변경 불가능/ 2: 1 변경가능
for rec in rectangle:
lbX,lbY,rtX,rtY = rec
lbX*=2
lbY*=2
rtX*=2
rtY*=2
for j in range(height):
for i in range(width):
# 내부
if j > lbY and j <rtY and i>lbX and i<rtX:
if graph[j][i] == '∙' or graph[j][i] == "◼︎":
graph[j][i] = "◻︎"
# 외각선 가로
if j == lbY or j == rtY:
if i >= lbX and i <= rtX:
if graph[j][i] == '∙':
graph[j][i] = "◼︎"
# 외각선 세로
if i == lbX or i == rtX:
if j >= lbY and j <= rtY:
if graph[j][i] == '∙':
graph[j][i] = "◼︎"
return [graph, width, height]
dx = [0,-1,0,1]
dy = [1,0,-1,0]
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
graph, w, h = check_rec_area(rectangle)
que = deque()
que.append([characterX*2, characterY*2, 0])
graph[characterY*2][characterX*2] = "◻︎"
# print("start")
# for g in graph[::-1]:
# print(g)
# print("")
while que:
popX, popY, count = que.popleft()
#graph[popY][popX] = "◻︎"
if popX == itemX*2 and popY == itemY*2:
answer = count
break
for n in range(4):
nx = popX + dx[n]
ny = popY + dy[n]
if w > nx >= 0 and h > ny >= 0 and graph[ny][nx] == "◼︎":
if nx % 2 == 0 and ny % 2 == 0:
que.append([nx, ny, count + 1])
graph[ny][nx] = "⚀"
else:
que.append([nx, ny, count])
graph[ny][nx] = "◻︎"
# for g in graph[::-1]:
# print(g)
# print(f"(count: {count + 1} x,y: {popX}, {popY})")
return answer
뿌듯하다 히히
'개발 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 프로그래머스 가장 큰 수(LV2) (1) | 2024.12.18 |
|---|