사각맵에서 가장 빨리 목적지로 도달하는 최단 경로 찾는 방법
1. 문제
https://programmers.co.kr/learn/courses/30/lessons/1844
코딩테스트 연습 - 게임 맵 최단거리
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
programmers.co.kr
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5*5 크기의 맵에, 당신의 캐릭터가 (행:1, 열:1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return하도록 solution 함수를 완성하세요.
단 상대 팀 진영에 도착할 수 없을 때는 -1을 return해주세요.
2. 제한사항
maps는 n*m 크기의 게임 맵의 상태가 들어있는 2차원 배열로 n과 m은 각각 1 이상 100이하의 자연수
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1,1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n,m) 위치에 있습니다.
3. 예시
4. 나의 풀이
먼저 (n,m-1)과 (n-1,m)에 벽이 있으면 들어갈 수 없으므로 이런 경우는 바로 -1을 return할 수 있도록 한다.
def solution(maps):
n = len(maps)
m = len(maps[0])
if (maps[n-2][-1] == 0) and (maps[n-1][-2] == 0):
return -1
else:
그런데 착각하면 안되는 것이 (n,m-1)과 (n-1,m)에 막혀있지 않더라도 절대로 못들어갈 수도 있다는 것이다
예를 들면 위와 같이 막혀도 절대로 못들어간다..
아무튼 상하좌우로 이동할 수 있으니까 상하좌우로 전부 이동시켜보면서 최솟값을 찾아나가는 BFS 방법을 사용하고자 한다.
말 그대로 현재 위치에서 가까운 노드를 모두 검사해보는 방법이다
그렇기 때문에 상하좌우로 이동하는 함수를 먼저 만든다
def solution(maps):
from collections import deque
def move_south(x,y,dir_len):
lock = False
x += 1
if x > n-1:
x -= 1
lock = True
else:
if maps[x][y] == 1:
dir_len += 1
else:
x -= 1
lock = True
return x,y,lock,dir_len
n = len(maps)
m = len(maps[0])
if (maps[n-2][-1] == 0) and (maps[n-1][-2] == 0):
return -1
else:
현재 좌표가 (x,y)라고 하고 이동한 경로의 최소길이가 dir_len이라고 하여 이들을 변수로 받는 함수 move_south
lock는 막혀서 진행불가라는 뜻의 지시변수
남쪽으로 1칸 이동하므로 행이 1이 더해지니까 x에 1을 더한다
왜냐하면 위에서부터 0행이라하고 맨 아래가 n행이니까
아무튼 1칸 이동했더니 x가 n-1보다 크다면 최대행이 n-1이니까 더 이상 이동할 수 없다는 뜻이므로 x에 1을 빼서 원래대로 되돌리고
lock = True로 하여 못간다고 알려준다
그렇지않다면 maps에서 현재 (x,y)의 상태를 알아본다
현재 (x,y)의 상태 maps[x][y]가 1이면 이동할 수 있다는 뜻이므로 경로의 길이 dir_len에 1을 더해주고
0이면 이동할 수 없는 곳에 이동했다는 뜻이므로 x에 1을 빼주고 lock을 True로 하여 x,y,lock,dir_len을 return
이런 방식으로 move_north, move_east, move_west를 모두 만들어준다
def solution(maps):
from collections import deque
def move_south(x,y,dir_len):
lock = False
x += 1
if x > n-1:
x -= 1
lock = True
else:
if maps[x][y] == 1:
dir_len += 1
else:
x -= 1
lock = True
return x,y,lock,dir_len
def move_north(x,y,dir_len):
lock = False
x -= 1
if x < 0:
x += 1
lock = True
else:
if maps[x][y] == 1:
dir_len += 1
else:
x += 1
lock = True
return x,y,lock,dir_len
def move_east(x,y,dir_len):
lock = False
y += 1
if y > m-1:
y -= 1
lock = True
else:
if maps[x][y] == 1:
dir_len += 1
else:
y -= 1
lock = True
return x,y,lock,dir_len
def move_west(x,y,dir_len):
lock = False
y -= 1
if y < 0:
y += 1
lock = True
else:
if maps[x][y] == 1:
dir_len += 1
else:
y += 1
lock = True
return x,y,lock,dir_len
n = len(maps)
m = len(maps[0])
if (maps[n-2][-1] == 0) and (maps[n-1][-2] == 0):
return -1
else:
그러면 이제 현재 위치 x=0,y=0으로 두고 칸 수를 셀건데 현재 위치 (0,0)도 1칸으로 세니까 dir_len = 1로 초기화
모든 검사하는 노드 경로를 담을 total_dir을 deque로 만들어준다
그리고 검사가 끝난 노드를 담을 집합 all_loc도 세팅을 한다
else:
x = 0
y = 0
num = 0
dir_len = 1
total_dir = deque([(x,y,dir_len,num)])
all_loc = set([(0,0)])
그러면 이제 total_dir에서 하나씩 빼서 상하좌우로 움직여서 검사를 해보고 이동할 수 있다면 total_dir에 넣고
검사가 끝난 노드는 중복 검사를 방지하기 위해 all_loc에 넣는다
이동할 수 없다면 total_dir에 넣을 필요가 없다
else:
x = 0
y = 0
num = 0
dir_len = 1
total_dir = deque([(x,y,dir_len,num)])
all_loc = set([(0,0)])
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
a,b,lock,new_dir = move_north(x,y,dir_len)
c,d,lock,new_dir = move_south(x,y,dir_len)
e,f,lock,new_dir = move_east(x,y,dir_len)
g,h,lock,new_dir = move_west(x,y,dir_len)여기서 num은 몇번째 경로를 의미하는지 나타내는 변수이다
현재 첫번째 (0,0) 위치는 0번째 경로라는 의미로 마지막에 num=0을 두는데
상하좌우로 이동하다보면 모두 이동가능하다면 결국 총 4가지 경우의 수로 될거잖어
아무튼 동서남북으로 이동하면서 만약 lock=False이면 이동가능하다는 뜻이므로
total_dir에 넣는다.
else:
x = 0
y = 0
num = 0
dir_len = 1
total_dir = deque([(x,y,dir_len,num)])
all_loc = set([(0,0)])
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False:
total_dir.append((a,b,new_dir,num))
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False:
total_dir.append((c,d,new_dir,num))
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False:
total_dir.append((e,f,new_dir,num))
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False:
total_dir.append((g,h,new_dir,num))
그런데 이제 이 상태에서 검사가 끝난 (a,b), (c,d), (e,f), (g,h)는 다시 검사하지 않도록 all_loc에 넣어줘야함
all_loc에 넣지 않으면 중복 검사하기 때문에 비효율적이 되니까
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False:
total_dir.append((a,b,new_dir,num))
all_loc.add((a,b))
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False:
total_dir.append((c,d,new_dir,num))
all_loc.add((c,d))
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False:
total_dir.append((e,f,new_dir,num))
all_loc.add((e,f))
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False:
total_dir.append((g,h,new_dir,num))
all_loc.add((g,h))
all_loc에 넣더라도 문제는 move하면서 all_loc에 넣은 좌표가 또 나오면 total_dir에 넣지말아야하는데
이러한 조건을 추가해줘야할 것이다
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False and not((a,b) in all_loc):
total_dir.append((a,b,new_dir,num))
all_loc.add((a,b))
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False and not((c,d) in all_loc):
total_dir.append((c,d,new_dir,num))
all_loc.add((c,d))
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False and not((e,f) in all_loc):
total_dir.append((e,f,new_dir,num))
all_loc.add((e,f))
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False and not((g,h) in all_loc):
total_dir.append((g,h,new_dir,num))
all_loc.add((g,h))
하지만 이렇게 하더라도 문제는 경로 구분을 하지 못한다는 점이다. 그것을 위해 num이라는 변수를 줄 것이고
before이라는 지시변수를 이용해서 이전 move 함수가 통과되면 before = True라 두고
before = True인 경우는 num에 1을 더해주면 경로 구분이 가능하다
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
before = False
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False and not((a,b) in all_loc):
before = True
total_dir.append((a,b,new_dir,num))
all_loc.add((a,b))
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False and not((c,d) in all_loc):
if before:
num += 1
before = True
total_dir.append((c,d,new_dir,num))
all_loc.add((c,d))
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False and not((e,f) in all_loc):
if before:
num += 1
before = True
total_dir.append((e,f,new_dir,num))
all_loc.add((e,f))
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False and not((g,h) in all_loc):
if before:
num += 1
total_dir.append((g,h,new_dir,num))
all_loc.add((g,h))중간에 before = False로 넣어줘야하는거 아니야??
생각을 해보면 move_north가 통과되지않으면 num = 0인데 before = False이고..
2번이 통과되면 여전히 num = 0으로 두고 before = True라 두고
3번이 통과되면 현재 before = True니까 num = 1로 될테고 total_dir에 넣은다음에 before = False로 해야하나??
그럴 필요가 없는게
4번이 통과되면 before = True이면 num = 2로 구분지어 주는게 맞고
4번이 통과안된다면 어차피 넣지 않을테니까 num이 1이든 2이든 상관없어
마찬가지로 1번이 통과되면 num=0을 넣고 before = True
2번이 통과되지않으면 num=0이든 1이든 상관없이 어차피 total_dir에 안넣을거니까 필요없고
여기서 before = False해야하냐?? 그럴 필요 없는게
3번이 통과되면 현재 before = True니까 num=1로 구분지어 넣는게 맞고
통과되지 않더라도 num=0이든 1이든 상관없이 안넣을거니까 before이 뭐든 상관없다
아무튼 이제 만약에 4가지 move를 하다가 그 중 어떤 것이라도 최종 지점인 (n-1,m-1)에 도달했다면 그것이 최소경로니까 바로 return하면 된다
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
before = False
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False and not((a,b) in all_loc):
before = True
total_dir.append((a,b,new_dir,num))
all_loc.add((a,b))
if a == n-1 and b == m - 1:
return new_dir
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False and not((c,d) in all_loc):
if before:
num += 1
before = True
total_dir.append((c,d,new_dir,num))
all_loc.add((c,d))
if c == n-1 and d == m-1:
return new_dir
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False and not((e,f) in all_loc):
if before:
num += 1
before = True
total_dir.append((e,f,new_dir,num))
all_loc.add((e,f))
if e == n-1 and f == m-1:
return new_dir
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False and not((g,h) in all_loc):
if before:
num += 1
total_dir.append((g,h,new_dir,num))
all_loc.add((g,h))
if g == n-1 and h == m-1:
return new_dir
그러면 이제 모든 total_dir을 다 검사했어.. lock이 되거나 node를 전부 지나보면 total_dir에 안들어가잖아
그런 뜻은? 최종 지점에 도달하지 못한다는 뜻
그러니까 반복문을 빠져나온다는 뜻은 결국 모든 total_dir을 검사했는데도 막혀있다는 뜻으로
최종지점에 도달하지 못한다는 뜻이다
while total_dir != deque():
x,y,dir_len,num = total_dir.popleft()
before = False
a,b,lock,new_dir = move_north(x,y,dir_len)
if lock == False and not((a,b) in all_loc):
before = True
total_dir.append((a,b,new_dir,num))
all_loc.add((a,b))
if a == n-1 and b == m - 1:
return new_dir
c,d,lock,new_dir = move_south(x,y,dir_len)
if lock == False and not((c,d) in all_loc):
if before:
num += 1
before = True
total_dir.append((c,d,new_dir,num))
all_loc.add((c,d))
if c == n-1 and d == m-1:
return new_dir
e,f,lock,new_dir = move_east(x,y,dir_len)
if lock == False and not((e,f) in all_loc):
if before:
num += 1
before = True
total_dir.append((e,f,new_dir,num))
all_loc.add((e,f))
if e == n-1 and f == m-1:
return new_dir
g,h,lock,new_dir = move_west(x,y,dir_len)
if lock == False and not((g,h) in all_loc):
if before:
num += 1
total_dir.append((g,h,new_dir,num))
all_loc.add((g,h))
if g == n-1 and h == m-1:
return new_dir
return -1
5. 다른 풀이
좋아요를 가장 많이 받은 풀이 분석
from collections import deque
def solution(maps):
x_move = [1, 0, -1, 0]
y_move = [0, 1, 0, -1]
x_h, y_h = (len(maps[0]), len(maps))
queue = deque([(0, 0, 1)])
while queue:
x, y, d = queue.popleft()
for i in range(4):
nx = x + x_move[i]
ny = y + y_move[i]
if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
maps[ny][nx] = d + 1
if nx == x_h - 1 and ny == y_h - 1:
return d + 1
queue.append((nx, ny, d + 1))
return -1
먼저 x_move, y_move는 상하좌우로 이동하기 위해 만든 리스트일테고
중간에 for문 보면 nx = x + x_move[i], ny = y + y_move[i]로 한거 보면
서로 위치가 대응하는 관계끼리 묶어서
(1,0)을 이동, (0,1)을 이동, (-1,0)을 이동, (0,-1)을 이동시킬거라는 것을 알 수 있단 말이지
x_h와 y_h는 x축 길이와 y축 길이인듯
나랑은 좀 반대로 생각한 것 같고.. 나는 x를 행의 이동 len(maps)로 구했고 y를 열의 이동 len(maps[0])로 구했잖아
from collections import deque
def solution(maps):
x_move = [1, 0, -1, 0]
y_move = [0, 1, 0, -1]
x_h, y_h = (len(maps[0]), len(maps))
queue = deque([(0, 0, 1)])
queue에 deque([(0,0,1)])은 while문 보면 x,y,d로 뺐는데 x,y는 현재 위치이고 d는 경로의 길이를 의미하는듯
다음 queue에서 빼서 for문을 돌건에 이동은 상하좌우 4가지니까 range(4)로 검사를 하는데
nx와 ny는 move를 하고 나서 얻은 좌표이고
nx가 -1보다 크고 x_h보다 작고, ny가 -1보다 크고 y_h보다 작다는 것은 맵 안에 존재한다는 뜻으로 유효한 이동이라는 뜻
만약 유효한 이동이라면 이제 실제로 벽에 이동한건지 그렇지 않은지 검사를 해보기 위해 maps에 넣을건데
ny는 y축 이동으로 행이동이고 nx는 x축 이동으로 열이동이니까 maps[ny][nx]를 구했다
---------------------------------------------------------------------------------------------------------------------
그리고 여기가 지리네
maps[ny][nx] == 1이라면 진짜로 이동이 가능한 지역이니까 maps[ny][nx]를 현재 경로의 길이 d에 1을 더한 d+1로 바꿔준다
그리고 maps[ny][nx]가 d+1보다 클 수도 있는데 그런 경우도 maps[ny][nx] = d+1로 둔다.
이걸 왜 해야하느냐?? 그렇게 생각할 수 있는데
이것의 의미를 한번 생각해보면
현재 deque에 위 그림같이 2가지 경우 (nx1, ny1,8), (nx2,ny2,8)이 들어가 있을 것이란 말이야
계속 이동을 해보면
1번 경로로 가면 8 9 10 11 12까지 일단 채우고
2번 경로로 가면 8 9 10 11로 채울텐데
문제는 1번 경로에서 12까지 채운 상태에서 다음 경로로 검사를 할 때 이미 2번 경로로 이동한 것에 의해서
다음 타일이 9로 채워져 있단 말이지
그러니까 현재 d = 12여서 d+1=13인데
다음으로 이동해야할 칸 maps[ny][nx] = 9여서
maps[ny][nx]가 1도 아니고 maps[ny][nx] >13 도 아니다
실제로 1번 경로로는 이동할 필요가 없다
문제는 maps[ny][nx] > d+1이어야하는 이유도 알겠지?
maps[ny][nx] > d+1이라는 것은 이전에 d+1보다 큰 값으로 채워진 경로는 최소 경로가 아니라는 뜻이고
현재 지나는 경로가 최소니까 그래서 maps[ny][nx] = d+1로 갱신하라는 의미다.
---------------------------------------------------------------------------------------------------------------------
while queue:
x, y, d = queue.popleft()
for i in range(4):
nx = x + x_move[i]
ny = y + y_move[i]
if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
maps[ny][nx] = d + 1
if nx == x_h - 1 and ny == y_h - 1:
return d + 1
queue.append((nx, ny, d + 1))
return -1
그리고 이동하다가 nx가 x_h-1이고 ny가 y_h-1이면 최종 지점에 도달했다는 의미이므로 바로 d+1을 return하면 끝
모든 queue를 검사했는데도 return하지 못하면 최종지점에 도달하지 못했다는 뜻이므로 반복문을 탈출하면
-1을 return하면 된다
6. 되돌아보기
결국에 나름대로 구현을 잘 하긴 했다
그런데 bfs와 dfs에 대해서 제대로 공부해서 정리해놓을 필요가 있겠다
인접한 경로를 모두 검사해나가는지?(bfs) 일단 한 경로를 정해서 쭈욱 검사해나가는지?(dfs)
그리고 검사하면 검사한 노드는 검사가 완료됐다는 뜻으로 따로 리스트에 저장해놔야한다는 점을 기억해야함
그리고 다른 풀이에서 if maps[ny][nx] == 1 and maps[ny][nx] > d+1 : maps[ny][nx] = d+1이 파고 들어보니까 지리네
'알고리즘 > 알고리즘 일반' 카테고리의 다른 글
| 파이썬은 big int는 지원하지만 big float를 지원하지 않는다 (0) | 2022.06.20 |
|---|---|
| 2진수 변환을 가장 빠르게 하는 방법 (0) | 2022.05.19 |
| 이차원 배열 회전시키는 방법 (0) | 2022.04.28 |
| 중복을 허용하는 집합 다루기 (0) | 2022.04.17 |
| 진수 변환 알고리즘 활용하기 (0) | 2022.04.16 |
