문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844
ROR 게임은 두 팀으로 나눠서 진행하는데, 상대 팀의 진영을 먼저 파괴하면 이긴다. 즉, 각 팀은 상대 팀 진영에 빠르게 도착해야 한다. 아래 그림은 당신의 팀 캐릭터(행 :1, 열 : 1), 상대 팀의 진영(행: 5, 열: 5) 그리고 게임의 맵(5 X 5)을 표현한 것이다.
맵에서 검은 부분은 벽으로 막혀 갈 수 없는 길이고, 흰 부분이 갈 수 있는 길이다. 캐릭터는 동서남북으로 한 칸씩 이동하되 맵을 벗어날 수는 없다. 만약 상대 팀 진영이 벽으로 막혀있다면 상대 팀 진영에 도착할 수 없다.
게임의 맵을 이차원 배열 maps 매개변수로 전달받을 때, 캐릭터가 상대 팀 진영에 도착하기 위해 지나야 하는 칸의 최소개수를 구하여라. maps는 0과 1로 이루어져 있고, 0은 벽이 있는 자리를, 1은 벽이 없는 자리를 나타낸다. 캐릭터는 맵의 좌측 상단 (1, 1)에, 그리고 상대 팀 진영은 맵의 우측 하단 (n, m)에 위치한다.
예로 들어 위의 예시의 경우, 캐릭터가 상대 팀 진영으로 가기 위해서는 두 가지 방법이 존재한다.
 |
 |
| 11개 칸을 지난다. | 15개 칸을 지난다. |
이때 반환해야 하는 값은 11이 된다. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 반환한다.
접근 / 풀이
전형적인 미로 찾기 문제로, 최단 경로를 찾아야 하므로 2024.05.08-[알고리즘] 너비 우선 탐색(BFS) 이란에서 살펴본 BFS를 적용하여 풀어낼 수 있다. 그래프 형식이 아니라 이차원 배열 형식인데, 조건문으로 방문 가능 여부를 확인하면 된다.
1. 값 초기화
방문한 위치를 저장할 queue와 방문 여부를 저장할 visited을 선언하고 초기화한다.
n = len(maps[0])
m = len(maps)
visited = [[0 for _ in range(n)] for _ in range(m)]
queue = [(0, 0)]
visited[0][0] = 1visited는 방문 지점까지 가기 위해 지나야 하는 칸의 수를 저장할 수 있도록 0으로 초기화했다.
2. 아래 과정을 큐가 빌 때까지 반복한다.
- 큐에서 방문한 위치를 꺼낸다.
i, j = queue.pop(0)
- 다음에 방문하는 칸의 위치를 확인하고 방문한 칸의 위치는 큐에 넣는다.
if i + 1 < m and maps[i + 1][j] == 1 and visited[i + 1][j] == 0:
queue.append((i + 1, j))
visited[i + 1][j] = visited[i][j] + 1방문하는 칸의 위치를 확인할 때는 인덱스가 맵 내에서 유효한지, 맵이 벽으로 막혀있지 않은지, 아직 방문하지 않은 위치인지를 확인해야 한다. 또한 방문한 지점까지의 가기 위해 지나야 하는 칸의 수 구하기 위해 방문 여부 갱신 시 해당 정보로 갱신하도록 한다.
해당 과정은 동서남북 방향으로 모두 수행해야 한다.
while queue:
i, j = queue.pop(0)
if i + 1 < m and maps[i + 1][j] == 1 and visited[i + 1][j] == 0:
queue.append((i + 1, j))
visited[i + 1][j] = visited[i][j] + 1
if j + 1 < n and maps[i][j + 1] == 1 and visited[i][j + 1] == 0:
queue.append((i, j + 1))
visited[i][j + 1] = visited[i][j] + 1
if i - 1 >= 0 and maps[i - 1][j] == 1 and visited[i - 1][j] == 0:
queue.append((i - 1, j))
visited[i - 1][j] = visited[i][j] + 1
if j - 1 >= 0 and maps[i][j - 1] == 1 and visited[i][j - 1] == 0:
queue.append((i, j - 1))
visited[i][j - 1] = visited[i][j] + 1
3. 반복을 완료하면 상대 팀 진영 방문 여부에 따라 값을 반환한다.
if visited[-1][-1] == 0:
return -1
return visited[-1][-1]전체 코드는 접은글로 적어둔다.
def solution(maps):
n = len(maps[0])
m = len(maps)
visited = [[0 for _ in range(n)] for _ in range(m)]
queue = [(0, 0)]
visited[0][0] = 1
while queue:
i, j = queue.pop(0)
if i + 1 < m and maps[i + 1][j] == 1 and visited[i + 1][j] == 0:
queue.append((i + 1, j))
visited[i + 1][j] = visited[i][j] + 1
if j + 1 < n and maps[i][j + 1] == 1 and visited[i][j + 1] == 0:
queue.append((i, j + 1))
visited[i][j + 1] = visited[i][j] + 1
if i - 1 >= 0 and maps[i - 1][j] == 1 and visited[i - 1][j] == 0:
queue.append((i - 1, j))
visited[i - 1][j] = visited[i][j] + 1
if j - 1 >= 0 and maps[i][j - 1] == 1 and visited[i][j - 1] == 0:
queue.append((i, j - 1))
visited[i][j - 1] = visited[i][j] + 1
if visited[-1][-1] == 0:
return -1
return visited[-1][-1]
🤔 동서남북 방향으로 방문하는 칸의 위치를 확인하고 있는데, 해당 코드가 비슷한 구조로 되어 있다.
불필요한 중복을 없애기 위해 반복문을 사용하는 편이 더 좋을 것 같다.
참고 문서
https://school.programmers.co.kr/learn/courses/30/lessons/1844