1. 문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임이다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리하다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길이다. 캐릭터는 동, 서, 남, 북으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없다.
첫번째 방법은 11칸을 지나서 도착이며, 두번째 방법은 15칸을 지나서 도착이다.
만약, 상대 팀이 자신의 티 진영 주변에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있다.
이때, 상대 팀 진영에 도착하기 위해 지나가야 하는 칸의 개수의 최솟값을 반환하여라.
2. 코드
(1) 1차 시도
dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌
minimum = 10001
def dfs(maps, now_r, now_c):
global minimum
n, m = len(maps), len(maps[0])
if (now_r == n-1) and (now_c == m-1): # 적 진영에 도착한 경우
if maps[now_r][now_c] < minimum:
minimum = maps[now_r][now_c]
return minimum
for i in range(4):
new_r = now_r + dr[i]
new_c = now_c + dc[i]
if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
if maps[new_r][new_c] == 1:
maps[new_r][new_c] = maps[now_r][now_c] + 1
dfs(maps, new_r, new_c)
maps[new_r][new_c] = 1
def solution(maps):
global minimum
now_r, now_c = 0, 0
dfs(maps, now_r, now_c)
if minimum == 10001:
return -1
return minimum
효율성 테스트를 통과하지 못했다.
(2) 2차 시도
from collections import deque
dr = [1, 0, -1, 0] # row : 하 우 상 좌
dc = [0, 1, 0, -1] # column : 하 우 상 좌
def bfs(maps, now_r, now_c):
n, m = len(maps), len(maps[0])
queue = deque()
queue.append([now_r, now_c])
while queue:
r, c = queue.popleft()
for i in range(4):
new_r = r + dr[i]
new_c = c + dc[i]
if new_r >= 0 and new_r <= (n-1) and new_c >= 0 and new_c <= (m-1):
if maps[new_r][new_c] == 0:
continue
if maps[new_r][new_c] == 1:
maps[new_r][new_c] = maps[r][c] + 1
queue.append([new_r, new_c])
return maps[n-1][m-1]
def solution(maps):
r, c = 0, 0
ans = bfs(maps, r, c)
if ans == 1:
return -1
return ans
3. 설명
BFS로 문제를 풀면, 어떻게 하더라도 계속 시간 초과가 발생한다ㅠㅠ
그래서 아예 DFS로 바꿔서 풀었다.
- deque를 사용하여 현재 위치를 큐에 넣어두고, popleft()를 하여 현재 위치를 받아온다.
- 현재 위치 기준 상, 하, 좌, 우를 이동하면서 맵을 벗어나지 않고 1 값을 가지는 위치 모두를 큐에 저장한다. → 너비 우선 방식!
- 큐에 저장된 [행, 열] 좌표에 대해 maps 배열의 원소를 이전 좌표에 +1 한 값으로 바꿔주어, 해당 좌표까지 오는데 얼만큼의 비용이 들어가는지 저장한다.
- 만약 dfs()에서 반환한 값이 1인 경우는 적의 진영에 도달하지 못했다는 의미이므로 -1을 반환한다.
1. 최솟값을 갱신해줄 필요가 없다.
- DFS는 최단경로를 보장한다.
2. visited로 방문 여부를 판단할 필요가 없다.
- maps의 값이 1일 때만 방문하도록 하여 따로 방문 여부를 저장하는 배열이 필요하지 않다,
'Algorithm' 카테고리의 다른 글
| 프로그래머스 > 모음사전 (Python 3) (1) | 2024.07.23 |
|---|---|
| 프로그래머스 > [3차] 압축 (Python 3) (0) | 2024.07.17 |
| 프로그래머스 > k진수에서 소수 개수 구하기 (Python 3) (0) | 2024.07.15 |
| 프로그래머스 > [3차] n진수 게임 (Python 3) (1) | 2024.07.14 |
| 프로그래머스 > 전화번호 목록 (Python 3) (0) | 2024.07.09 |
