문제
문제 설명
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로 탐색하면서, 경로를 넣어준다는 것이다.
정답 코드
from collections import deque
def solution(maps):
## 상대방이 있는 위치
n = len(maps)-1
m = len(maps[0])-1
## 동서남북 이동을 정의
dx = [0, 0, 1, -1] ## 행
dy = [1, -1, 0, 0] ## 열
## bfs를 위한 queue 초기화
queue=deque([(0,0)])
while queue:
x, y = queue.popleft() ## 현재 위치
# print("***")
# print(x, y)
# print(maps[x][y])
## 동서 남북으로 이동하기
for i in range(4):
nx, ny = x+dx[i], y+dy[i]
## 맵을 벗어난 경우는 무시하기
if nx < 0 or nx > n or ny < 0 or ny > m:
continue
## 벽인 경우는 무시하기
if maps[nx][ny] == 0:
continue
## 갈 수 있는 경우에는 큐에 넣고 최단경로를 기록하기 (이미 방문한 경우는 고려하지 않기)
if maps[nx][ny] == 1:
queue.append((nx, ny))
maps[nx][ny] += maps[x][y]
if maps[n][m] > 1:
answer = maps[n][m]
else:
answer = -1
return answer
- x는 행을 의미하고, y는 열을 의미한다. 따라서 x는 위아래로의 움직임을 의미하고, y는 오른쪽 왼쪽으로의 움직임을 의미힌다. 현 위치에서 동,서,남,북으로 이동하는 것은 dx, dy로 정의해놓는다.
- 큐를 통해 bfs를 구현한다. 현재 위치부터 넣어주고, 이동이 가능한 곳을 그 다음에 넣어서 순차적으로 현재까지의 최단 경로가 어떻게 되었는지 확인할 수 있게 한다. 특히 한 번 간 곳은 더 이상 방문하지 않기 때문에 오른쪽->아래쪽으로 퍼져나가는 최단 경로에서는 최종적으로 올바른 최단 경로를 저장될 수 있게 된다.
느낀 점
- 대표적인 BFS 유형이기 때문에 까먹지 않고 응용할 수 있도록 하는 것이 중요할 것 같다.
- 은근히 행, 열 그리고 조건 넣을 때 헷갈렸다. 2차원 배열에서의 움직이는 시나리오에 익숙해질 필요가 있을 거 같다. (index 에러가 나지 않도록!)
