알고리즘 문제 풀이 - 아이템 줍기
서론
코딩테스트를 지속적으로 1문제씩 풀다가 최근에 진행한 프로젝트 이후로 잘 안 풀게 된 것 같아서 다시 한번 감을 잡아볼 겸 프로그래머스 알고리즘 고득점 Kit 중에서 풀지 않은 문제를 풀어보았다. BFS/DFS 유형에 있는 LV3 문제인 아이템 줍기를 풀어봤는데 그 과정에서 배운 것을 정리해보려고 한다.
접근 과정
유형부터 생각해보자면 시작점부터 끝 점 까지의 최단거리를 구해야하는 BFS 유형이다. 경로는 모두 사각형의 테두리위에 존재한다. 사각형이 존재할 수 있는 좌표평면의 크기가 최대 50*50이고 사각형은 최대 4개 존재하기 때문에 모든 경로를 탐색할 수 있다.
여기서 핵심 포인트는 사각형 내부의 테두리의 경로는 이용할 수 없다는 점이다. 어떻게 하면 테두리의 내부로 가는 경로를 판단할 지를 잘 생각해봐야한다.
사각형이 직교하는 점에 대해서는 동서남북으로 모두 4가지의 경로가 존재한다. 나는 모든 다음 갈 경로에 대해서 어떤 사각형의 테두리인지를 기록해 놓고 사각형 둘이 직교할 때 바로 이전의 사각형과 같은 경로라면 가지 않고 다른 경로라면 이전 사각형의 내부가 아닌 점으로 가도록하여 최종적으로 직교하는 점에서 하나의 경로로 가도록 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
from collections import deque
def is_in(t_y, t_x, r):
s_x, s_y, e_x, e_y = r
#print()
if s_y <= t_y <= e_y and s_x <= t_x <= e_x:
#print('내부임', t_y,t_x, r)
return True
#print('내부 아님', t_y,t_x, r)
return False
def make_map(cmap, sx, sy, ex, ey, i):
for y in range(sy, ey):
cmap[y][sx].append((y+1,sx,i))
cmap[y+1][sx].append((y,sx,i))
cmap[y][ex].append((y+1,ex,i))
cmap[y+1][ex].append((y,ex,i))
for x in range(sx, ex):
cmap[sy][x].append((sy,x+1,i))
cmap[sy][x+1].append((sy,x,i))
cmap[ey][x].append((ey,x+1,i))
cmap[ey][x+1].append((ey,x,i))
def bfs(cmap, sy, sx, ty, tx, rectangle):
visited = set()
q = deque()
visited.add((sy,sx))
q.append((sy,sx,0,set([0]))) # 0을 처음 사각형으로 두는 꼼수.. 그러나 실패
print(ty, tx)
while q:
y,x,l,r = q.popleft()
# print(y,x,l,r)
# print('next:',cmap[y][x])
if y == ty and x == tx:
return l
r_set = set()
for _, __, i in cmap[y][x]: # 현재 위치의 겹치는 사각형 구하기
r_set.add(i)
for yy,xx,i in cmap[y][x]:
# 방문했던 곳 가지 않음
if (yy,xx) in visited:
continue
# 갈림길
if len(cmap[y][x]) > 2:
# 이전 사각형 이어진 길은 가지 않음
if i in r:
continue
# 두 개의 길 중 이전 사각형 내부의 길(테두리 포함)
inner = False
for i in r:
if is_in(yy,xx, rectangle[i]):
inner = True
break
if inner:
continue
# 다음 방문
visited.add((yy,xx))
q.append((yy,xx,l+1,r_set))
print(visited)
def solution(rectangle, characterX, characterY, itemX, itemY):
cmap = [[[] for _ in range(101)] for _ in range(101)]
for i, v in enumerate(rectangle):
sx, sy, ex, ey = v
make_map(cmap, sx, sy, ex, ey, i)
for m in cmap[:6]:
print(m[:6])
result = bfs(cmap, characterY, characterX, itemY, itemX, rectangle)
print(result)
return result
그런데 이 방법은 처음부터 직교하는 점에서 시작할 시에 어느 경로로 가야할 지 알 수가 없어서 예외 케이스가 존재했다.
뭔가 더 복잡한 로직을 세우면 첫 점이 직교하는 점이더라도 판단할 수 있을 것 같긴 하지만 다른 사람들의 풀이가 궁금해서 다른사람들의 풀이를 찾아보았다.
다른 사람들의 풀이
경로를 처음부터 테두리가 아닌 것을 제외하기
보고나서 약간 허탈했다. 시간복잡도도 널널하겠다 그냥 처음부터 모든 사각형을 순회하면서 내부의 테두리는 경로에서 제외하면 되는 것이었다. 정확히 어떤 사각형의 내부의 점인지 판단하는 로직이 아주 약간은 더 시간이 빠를 수는 있겠지만 구현의 난이도는 훨씬 복잡해지기 때문에 전자의 방법이 훨씬 옳은 접근방법이었다.
좌표 2배로 늘이기
나도 역시 다른 사각형과 거리가 1차이가 나는 부분에서 오류를 겪었었는데 이 부분을 다음 노드를 직접 가리키도록 그래프 정보를 만들어서 해결했었다. 근데 이런 창의적인 방법이 존재한다는 것이 신기했다.
이 방법이 유용한 이유는 또 있다. 직교하는 사각형을 만나게 되면 원래 이전에 갈 수 있었던 경로가 내부의 점이 되어 갈 수 없게 되지만, 평행한 테두리의 길이가 1일 경우에는 테두리 내부의 점이 아니라 정확히 테두리에 걸치는 점이기 때문에 이를 판단하기 어렵게 된다. 하지만 좌표를 2배로 늘리면 테두리의 최소 길이가 2이기 때문에 이 이역시도 해결이 되는 것이다.
좌표를 2배로 늘리는 방법.. 기억했다가 언젠간 유용하게 써먹을 수 있을 것 같다.
선분으로 접근하기
현재 내부의 점인지 판단하는 것은 좌표를 이용하기 때문에 테두리 길이가 1인 경우에는 판단을 할 수가 없다. 따라서 선분으로 접근하여 길이가 1인 선분이 내부에 존재한다면 길이가 1이더라도 판단할 수가 있다. 이 접근방법이 어떻게 보면 더 직관적이라고도 할 수 있을 것 같다.
최종 코드
해서 최종적으로는 나도 좌표를 2배를 늘리고 처음부터 내부의 점을 제거하는 방법을 선택했다. 사실 2배로 늘리면 그래프 정보를 2차원으로 간단하게 나타낼 수도 있지만 기존의 코드에서 이전에 다음 방문할 노드를 직접 저장하는 방식으로 그래프 정보를 만들었기 때문에 이는 유지하였다.(쓸데없는 고집 때문에 코드가 좀 길어짐..🙂)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
from collections import deque
def is_in(t_y, t_x, r):
s_x, s_y, e_x, e_y = r
if s_y < t_y < e_y and s_x < t_x < e_x:
return True
return False
def make_map(rectangle, cmap, sx, sy, ex, ey, i):
for y in range(sy, ey):
for osx, osy, oex, oey in rectangle:
if osy < y+1 < oey and osx < sx < oex:
break
else:
cmap[y][sx].append((y+1,sx,i))
cmap[y+1][sx].append((y,sx,i))
for osx, osy, oex, oey in rectangle:
if osy < y+1 < oey and osx < ex < oex:
break
else:
cmap[y][ex].append((y+1,ex,i))
cmap[y+1][ex].append((y,ex,i))
for x in range(sx, ex):
for osx, osy, oex, oey in rectangle:
if osy < sy < oey and osx < x+1 < oex:
break
else:
cmap[sy][x].append((sy,x+1,i))
cmap[sy][x+1].append((sy,x,i))
for osx, osy, oex, oey in rectangle:
if osy < ey < oey and osx < x+1 < oex:
break
else:
cmap[ey][x].append((ey,x+1,i))
cmap[ey][x+1].append((ey,x,i))
def bfs(cmap, sy, sx, ty, tx, rectangle):
visited = set()
q = deque()
visited.add((sy,sx))
q.append((sy,sx,0))
while q:
y,x,l = q.popleft()
# print(y,x,l,r)
if y == ty and x == tx:
return l
for yy,xx,i in cmap[y][x]:
# 방문했던 곳 가지 않음
if (yy,xx) in visited:
continue
# 다음 방문
visited.add((yy,xx))
q.append((yy,xx,l+1))
def scale_up(rectangle):
for i, r in enumerate(rectangle):
for j in range(4):
rectangle[i][j] = r[j]*2
return rectangle
def solution(rectangle, characterX, characterY, itemX, itemY):
scale_up(rectangle)
cmap = [[[] for _ in range(102)] for _ in range(102)]
for i, v in enumerate(rectangle):
sx, sy, ex, ey = v
make_map(rectangle, cmap, sx, sy, ex, ey, i)
# for m in cmap[:12]:
# print(m[:12])
result = bfs(cmap, characterY*2, characterX*2, itemY*2, itemX*2, rectangle)
return result//2
결론
- 좌표로 정보를 나타낼 시에 바로 인접한 좌표에 존재하지 않는 경로를 만들거나, 어떤 좌표 내부를 확인할 때 애매한 상황이 존재할 수 있다.
- 이를 좌표를 2배 늘리는 방법을 선택하여 인접한 좌표를 존재하지 않게 하거나 선분 정보를 이용하는 것으로 해결할 수 있다.