✅ Programmers LV 2
🎈 리코쳇 로봇
보드게임 내 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는 지 말하는 게임.
움직이는 이동횟수는 한번 상/하/좌/우 중 한 곳을 선택했을 때 그 방향으로 이동할 수 있는 만큼 끝까지 이동한다. (다음 위치가 장애물, 맨 끝인 경우 1번)
.은 빈공간, R은 로봇 첫 위치, D는 장애물 위치, G는 목표지점.
(다음 위치가 목표 지점이어도 장애물이나 맨 끝이 아니면 그냥 넘어감.)
from collections import deque
def solution(board):
rx, ry = 0, 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
if board[i][j] == 'R':
rx, ry = i, j
def bfs():
queue = deque()
queue.append((rx, ry))
visited = [[0]*n for _ in range(m)]
visited[rx][ry] = 1
while queue:
x, y = queue.popleft()
if board[x][y] == 'G':
return visited[x][y] - 1
for i in range(4):
nx, ny = x, y
while True:
nx += dx[i]
ny += dy[i]
if 0<=nx<m and 0<=ny<n and board[nx][ny] == 'D':
nx -= dx[i]
ny -= dy[i]
break
if nx<0 or nx>=m or ny<0 or ny>=n:
nx -= dx[i]
ny -= dy[i]
break
if not visited[nx][ny]:
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))
return -1
return bfs()< 풀이 과정 >
전형적인 그래프 문제.
백준에서 구슬탈출? 문제를 풀었던게 바로 생각났다. 그래프 내 한 칸씩 이동이 아닌 벽이나 장애물을 만날때까지 이동을 구현시켜주는 방법.
- 주어진 board의 행, 열 길이를 이용해 시작 지점 확인 후 rx, ry로 저장
- bfs 함수 만들어 경로 탐색 실행.
2-1. deque 과 방문한 장소 확인하는 2차원 배열 visited 생성
2-2. deque에서 (x,y) 원소 빼면서 다음 장소가 G 도착지면 결과 리턴
2-3. 상하좌우 4방향을 탐색하며 while문으로 벽 또는 장애물 끝까지 이동하는 것 반영.
2-4. 주어진 범위이고 다음 위치가 D 또는, 범위를 벗어나면 이전 위치로 되돌리고 끝까지 가는 것 중단.
2-5. 방문하지 않은 곳이면 visited+1, queue에 삽입.
2-6. bfs 함수로 갈 수 없는 곳인 경우엔 -1 리턴되도록 설계- 결과적으로 bfs함수 실행결과 리턴
🎈 미로탈출
직사각형 격자 형태의 미로에서 탈출하고자 한다. 각 칸은 통로나 벽으로 구성되어있고 벽은 못 지나간다.
통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데 해당 문은 레버를 당겨야 열 수 있다.
따라서 출발지점에서 레버가 있는 칸으로 이동해 레버를 당긴 후 미로를 빠져나가는 문으로 이동하면 된다. (레버를 당기지 않았다면 출구가 있는 칸을 지날 수 있다.)
결과적으로 미로를 빠져나가는데 걸리는 시간을 구하는 문제.
시작 지점 : S, 출구 : E, 레버 : L, 통로 : O, 벽 : X
from collections import deque
def bfs(start, end, maps):
queue = deque()
m = len(maps)
n = len(maps[0])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[False]*n for _ in range(m)]
sx, sy = 0, 0
for i in range(m):
for j in range(n):
if maps[i][j] == start:
sx, sy = i, j
queue.append((sx, sy, 0))
while queue:
x, y, time = queue.popleft()
if maps[x][y] == end:
return time
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<m and 0<=ny<n and maps[nx][ny] != 'X':
if not visited[nx][ny]:
visited[nx][ny] = True
queue.append((nx, ny, time + 1))
return -1
def solution(maps):
path1 = bfs('S', 'L', maps)
path2 = bfs('L', 'E', maps)
if path1 != -1 and path2 != -1:
return path1 + path2
else:
return -1< 풀이 과정 >
핵심적인 것은 기존과 달리 bfs함수를 2회 사용해야 하는 문제
따라서 bfs함수 내 변수를 추가하여 구현하였다.
- bfs(start, end, maps)로 두고 일반적인 bfs함수를 생성
- deque에는 현 좌표와 time을 저장해주고 while문으로 queue를 반복하며 다음 위치가 종료 지점이면 time을 리턴하도록 구현해준다.
- 다음 위치가 방문하지 않은 곳이라면 visited(다음 위치) = True, queue에 다음 위치와 time + 1을 삽입해준다.
- solution 함수로는 2개의 bfs 결과를 변수로 저장해주고 둘다 -1이 아니면 두 변수의 합을, 둘 중 하나라도 변수가 -1이라면 -1을 리턴하도록 해주어야 한다. (bfs의 결과가 -1이면 이동 X라는 것을 의미.)
To be a DataScientist