게임 맵 최단거리
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
| maps | answer |
|---|---|
| [[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 |
🥨 BFS 정답 풀이
최단거리를 구하는 문제는 BFS로 푸는 것을 알았지만
접근 방법을 몰랐...
# 스타트 지점은 항상 0,0 이고
# 도착지점은 항상 n,m
def solution(maps):
n, m = len(maps)-1, len(maps[0])-1
answer = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = []
queue.append([0,0])
while queue: #queue 가 빌 때까지
now = queue.pop(0)
x = now[0]
y = now[1]
for i in range(4): #상하좌우
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx<= n and 0<=ny<=y and maps[nx][ny] ==1:
#범위가 좌표 밖으로 안넘어가고 좌표가 1인 경우
maps[nx][ny] = maps[x][y] + 1 # 한칸 전진
queue.append((nx,ny)) # 새로운 좌표
destination = maps[n][m]
if destination == 1:
answer = -1
else:
answer = destination
return answer - 입력으로 주어지는 maps와 같은 크기를 가진 check배열을 만들어 -1으로 채워줍니다.
- 상단의 dd배열을 이용하여 시작 지점인 0,0 자리부터 상하좌우 방향을 탐색하여 방문할 수 있는 곳인 1을 찾아 queue에 추가 해줍니다.
- 방문할 수 있는 곳을 찾아 해당 지점으로 이동을 하면서 check의 같은 지점에 1을 더해주어 해당 지점까지 최소 거리를 확인 해줍니다.
dd = [[1,0],[0,1],[-1,0],[0,-1]]; #상하좌우
def solution(maps):
y = len(maps); #배열의 개수를 가지고 y값
x = len(maps[0]); #배열 안의 값의 개수를 가지고 x값
check = [[ -1 for _ in range(x) ] for _ in range(y)];
#map과 같은 크기의 check 배열을 -1 초기화
check[0][0] = 1
#시작 지점인 0,0 에는 무조건 방문함으로 1으로 직접 입력
queue = []
queue.append([0,0]); #queue에 시작점인 0,0
while queue: #queue에 값이 없어질 때 까지 반복합니다.
b, a = queue.pop(0); #queue의 값을 꺼내어와 값을 변수에 담아 줍니다.
for i in range(4): #네 방향을 모두 확인해 줍니다.
dy = b + dd[i][0];
dx = a + dd[i][1];
if -1<dx<x and -1<dy<y: #dx, dy가 map배열의 범위를 벗어나지 않는다면 확인을 시작합니다.
if maps[dy][dx] == 1: #maps[dy][dy]가 벽으로 막혀있지 않고(값이 1이고)
if check[dy][dx] == -1: #아직 방문하지 않은 곳이라면(check[dy][dx]가 -1이라면
print(dy,dx)
check[dy][dx] = check[b][a] + 1; #해당 위치를 방문합니다. 해당 위치는 지금 위치보다 한칸 앞으로 간 상태이므로 +1 해줍니다.
queue.append([dy,dx]); #해당 위치에 방문하기 위해 queue에 담아줍니다.
answer = check[-1][-1]; #위의 while문이 종료되면 도착지점의 값에 대한 최단거리 값이 나타나게 됩니다.
return answerfrom collections import deque # deque 선언
def solution(maps):
dx = [-1,1,0,0]
dy = [0,0,-1,1] #거리 이동을 위한 이동 좌표 설정
row = len(maps) # 맵의 크기를 알기위한 변수 설정 1 - 행, 가로
col = len(maps[0]) # 맵의 크기를 알기위한 변수 설정 2 - 열, 세로
q = deque() # 자료구조 선언
q.append((0,0))
while q: # 해당 while의 경우 q가 빌 때까지
x,y = q.popleft() # 들어온 순서대로 가져오기
for i in range(4): # 4방위 탐색
nx = x + dx[i]
ny = y + dy[i]
if 0<= nx < row and 0<= ny < col and maps[nx][ny] == 1:
# 주어진 맵을 벗어나는지 확인,탐색된 지역이 아닌 경우
maps[nx][ny] = maps[x][y] +1 # 이전 블럭에서 값 +1 해주기
q.append((nx,ny)) # 해당 nx,ny를 deque에 넣어주기
if maps[row-1][col-1] != 1: # 만약 1이 아니라면 해당 경우는 가로막히지 않은 경우
return maps[row-1][col-1] # 값 리턴
else:
return -1 # 가로막혀서 접근 불가인 경우 -1 리턴from collections import deque
def solution(maps):
n = len(maps); m = len(maps[0])
visited = [[False]*m for _ in range(n)]
q = deque()
q.append((0, 0))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited[0][0]=True
print(visited)
while q:
y, x = q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<m and 0<=ny<n and maps[ny][nx] == 1:
if not visited[ny][nx]: # False라면
visited[ny][nx] = True
q.append((ny, nx))
maps[ny][nx] = maps[y][x]+1
if maps[n-1][m-1]==1:
return -1
else:
return maps[n-1][m-1]from collections import deque
def solution(maps):
# n -> 미로의 행 수
map_rows = len(maps)
# m -> 미로의 열 수
map_columns = len(maps[0])
# 방문 여부를 저장하기 위한 2차원 배열
visited = [[False] * map_columns for _ in range(map_rows)]
#visited = []
# for i in range(map_rows):
# visited.append([False] * map_columns)
print(visited)
# 상하좌우 이동 방향을 정의 : 각 오른쪽, 왼쪽, 아래, 위임.
direction = [[1,0], [-1,0], [0,1], [0,-1]]
# 시작 노드를 큐에 추가
queue = deque([(0, 0, 1)]) # (x, y, 이동 횟수)
visited[0][0] = True
while queue:
x, y, count = queue.popleft()
# 도착 노드에 도달하면 이동 횟수 반환
# 왜 -1 씩 해줘야 하냐면 index가 전부 0부터 시작하기 때문에 -1 해줘야 함
if x == map_rows - 1 and y == map_columns - 1:
return count
# 상하좌우 이동을 검사
for i in direction:
row_x = x + i[0]
column_y = y + i[1]
# 미로 범위 내에 있고, 길이고 아직 방문하지 않았고 길이 연결되어 있을 때
if 0 <= row_x < map_rows and 0 <= column_y < map_columns and not visited[row_x][column_y] and maps[row_x][column_y] == 1:
# 방문 처리
visited[row_x][column_y] = True
# 큐에 추가
queue.append((row_x, column_y, count + 1))
# 도착점에 도달하지 못한 경우
return -1BFS로 접근하려면 queue.pop(0)
DFS로 접근하려면 queue.pop(-1)
Hi