![[BJ13460] 구슬 탈출2](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fcpod40%2FbtrAuNeUb9W%2FBcro4NF32NTv95K6XJ3KVk%2Fimg.png)
🚩 문제 설명
https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
⏱️ 시간 복잡도
▪ 상하좌우 움직인다면 X 4
▪ 보드에서 움직이므로 O(4NM)
◾ 빨간구슬만 특정하여 보드 내에서 탈출시키는 문제
◾ 파란구슬은 탈출하지 못하도록 예외 처리가 필요합니다. 이는 -1 을 출력해야합니다.
◾ 상하좌우를 움직인다면 구슬은 한 칸만 움직이는 것이 아니라, 중력에 의해 벽에 닿을 때 까지 움직입니다.
✅ 입출력
변수 설명
1. n m : 보드의 세로 x 가로
2. m 개의 요소를 가진 n 개의 줄이 주어짐
return ➡️ 상하좌우 움직여 최소로 빨간구슬을 탈출시킨 횟수
✔️ 예제 1
5 5
#####
#..B#
#.#.#
#RO.#
#####1
✔️ 예제 2
7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######5
✔️ 예제 3
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########-1
✔️ 예제 4
10 10
##########
#.......O#
#.#.....B#
#........#
#........#
##.......#
#....#..R#
#.##.....#
#........#
##########4
📑 문제 풀이
with 파이썬 (Python)
#sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
# 보드 크기 n x m (세로가로)
n, m = map(int, input().split())
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 방문 (빨간/파란구슬 위치 4개)
visited = [[[[0] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
# 이동거리 함수
def move(i, j, x, y):
cnt = 0
# '.' -> 쭉 한방향으로 움직인다
# 'O' -> 움직이는 것을 멈춘다
while a[i + x][j + y] != '#' and a[i][j] != 'O':
i += x
j += y
cnt += 1
return i, j, cnt
def bfs():
# 만약 while 문에서 빠져나가지 않았다면 -1 출력
while q:
Ri, Rj, Bi, Bj, cnt = q.popleft() # 방문시 큐에서 꺼내기
# 10번 이상
if cnt > 10:
break
# 상하좌우 움직이기
for i in range(4):
# 한방향 이동 후 빨간구슬 위치, 이동거리
ri, rj, rc = move(Ri, Rj, dx[i], dy[i])
# 한방향 이동 후 파란구슬 위치, 이동거리
bi, bj, bc = move(Bi, Bj, dx[i], dy[i])
# 파란구슬은 빠지지 않아야 한다 - 이외는 예외처리됨
if a[bi][bj] != 'O':
# 파란구슬은 탈출한다면
if a[ri][rj] == 'O':
print(cnt)
return
# 굴러서 같은 위치에 있다면 - 정위치를 찾아줘야한다.
# 한자리에 구슬 두 개가 동시에 있을 수는 없으니까
if all([ri == bi, rj == bj]):
if rc > bc:
ri -= dx[i]
rj -= dy[i]
else:
bi -= dx[i]
bj -= dy[i]
# 방문 처리
if visited[ri][rj][bi][bj] == 0:
q.append([ri, rj, bi, bj, cnt + 1]) # 방문가능 경로 큐에 넣기
visited[ri][rj][bi][bj] = 1
# -1 예외 처리
print(-1)
if __name__ == '__main__':
a = [] # 보드맵
R, B = (), () # 빨간/파란구슬 위치
# 보드 입력
for i in range(n):
tmp = input().strip()
R_ = tmp.find('R')
B_ = tmp.find('B')
if R_ != -1: # 빨간구슬 위치
R = i, R_
if B_ != -1: # 파란구슬 위치
B = i, B_
a.append(tmp)
# 보드 출력 확인
# for x in a:
# print(x)
# print(R, B)
# 탐색
q = deque() # bfs를 사용하기 위하여 큐 생성
q.append([R[0], R[1], B[0], B[1], 1])
visited[R[0]][R[1]][B[0]][B[1]] = 1 # 처음위치 방문처리
bfs()💬 Point
➡️ BFS() 를 사용한다.
➡️ BFS는 queue 를 이용하여 방문처리를 한다.
◾ 우선 문제를 풀기 전에 우리는 BFS 에 대해서 다시 한번 상기를 할 필요가 있다.
https://yeomss.tistory.com/118?category=924289
[이코테] DFS/BFS
목차는 다음과 같다. 1. 탐색이란? 2. DFS 3. BFS ✅ 탐색이란? (Search) 알고리즘에서 탐색 개요 ◾ 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 ◾ 프로그래밍에서는 그래프, 트리 등의 자료
yeomss.tistory.com
◾ BFS의 구조
from collections import deque
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5],
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]
visited = [0] * 9
def BFS(graph, start, visited):
queue = deque([start])
visited[start] = 1
while queue:
v = queue.popleft()
print(v, end = ' ')
for i in graph[v]:
if visited[i] != 1:
queue.append(i)
visited[i] = 1
BFS(graph, 1, visited)BFS 구조를 크게크게 덩어리 지어 문자로 표시해보면 다음과 같습니다.
1. 큐를 생성
2. 큐에 요소 추가
3. 방문 처리
4. while 문 돌기
1) popleft()
2) print()
3) for 문 돌기
i) 방문처리
- 큐에 요소 추가
- 방문 처리해당 구조를 잘 기억하고 본 문제에 적용을 해봅니다.
◾ 예시
1) 좌로 이동
2) 아래로 이동
3) 우로 이동
4) 아래로 이동
5) 좌로 이동
총 5번 만에 빨간구슬이 탈출에 성공하게 됩니다.
◾ 보드 크기를 입력받습니다. 또한 상하좌우로 움직여야하기때문에 간소화하기 위해서 dx, dy 의 방향키 또한 배열로 만들어놓아줍니다.
각각 (-1, 0), (1, 0), (0, -1), (0, 1) 이런식으로 움직입니다.
그리고 bfs() 를 방문을 나타내기 위해서 visited 배열을 추가해줍니다.
구슬들의 위치를 나타내기 위하여 4차원 배열 선언을 합니다.
# 보드 크기 n x m (세로가로)
n, m = map(int, input().split())
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 방문 (빨간/파란구슬 위치 4개)
visited = [[[[0] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
◾ 벽까지 쭉 이동을 할 이동거리 함수를 만들어줍니다.
매개변수로는 구슬의 현재 위치와 방향이 들어옵니다. 구슬들 각각 move() 함수를 적용할 예정입니다.
# 이동거리 함수
def move(i, j, x, y):
cnt = 0
# '.' -> 쭉 한방향으로 움직인다
# 'O' -> 움직이는 것을 멈춘다
while a[i + x][j + y] != '#' and a[i][j] != 'O':
i += x
j += y
cnt += 1
return i, j, cnt
◾ 보드맵을 입력받습니다.
또한, 빨간/파란구슬의 위치도 확인해야합니다. 문자열의 find() 함수를 사용했습니다.
bfs() 를 사용하기 위해서 queue 를 생성하고 큐 안에 처음 요소를 추가합니다.
추가한 요소를 방문 처리 합니다.
if __name__ == '__main__':
a = [] # 보드맵
R, B = (), () # 빨간/파란구슬 위치
# 보드 입력
for i in range(n):
tmp = input().strip()
R_ = tmp.find('R')
B_ = tmp.find('B')
if R_ != -1: # 빨간구슬 위치
R = i, R_
if B_ != -1: # 파란구슬 위치
B = i, B_
a.append(tmp)
# 보드 출력 확인
# for x in a:
# print(x)
# print(R, B)
# 탐색
q = deque() # bfs를 사용하기 위하여 큐 생성
q.append([R[0], R[1], B[0], B[1], 1])
visited[R[0]][R[1]][B[0]][B[1]] = 1 # 처음위치 방문처리
bfs()
◾ bfs 를 사용하려면 우선 while q: 가 필요합니다.
방문시 큐에서 우선 꺼내고 상하좌우를 움직이며 각 구슬의 위치와 이동거리를 알아냅니다.
상/하/좌/우 4번씩 돕니다. 만약 각각 돌아서 그 자리가 'O' 라면 cnt 를 출력합니다.
기본적으로 파란구슬은 탈출하지 않아야하기 때문에 if a[bi][bj] != 'O' 조건을 달아줍니다.
만약 해당 조건이 아니라면 예외 처리 -1 이 됩니다.
알고리즘상 중력으로 벽까지 각각 굴리는 것이기 때문에 빨간구슬, 파란구슬 위치가 같을 수가 있습니다.
이러면 각 위치를 조정해줍니다.
위치를 조정해줄 때 rc, bc 를 쓰는 이유는 구슬이 굴러갈때 이동거리가 더 큰 놈이 뒤에 오기 때문입니다.
그리고 마지막으로 방문처리를 해줍니다.
방문처리에서는 큐에 요소를 추가하고 visited 배열에 1 을 처리합니다.
큐에 요소를 넣을 때는 cnt + 1 을 해줘야합니다. while 문과 for 문 돌때마다 구슬을 움직이는 것이니.
def bfs():
# 만약 while 문에서 빠져나가지 않았다면 -1 출력
while q:
Ri, Rj, Bi, Bj, cnt = q.popleft() # 방문시 큐에서 꺼내기
# 10번 이상
if cnt > 10:
break
# 상하좌우 움직이기
for i in range(4):
# 한방향 이동 후 빨간구슬 위치, 이동거리
ri, rj, rc = move(Ri, Rj, dx[i], dy[i])
# 한방향 이동 후 파란구슬 위치, 이동거리
bi, bj, bc = move(Bi, Bj, dx[i], dy[i])
# 파란구슬은 빠지지 않아야 한다 - 이외는 예외처리됨
if a[bi][bj] != 'O':
# 파란구슬은 탈출한다면
if a[ri][rj] == 'O':
print(cnt)
return
# 굴러서 같은 위치에 있다면 - 정위치를 찾아줘야한다.
# 한자리에 구슬 두 개가 동시에 있을 수는 없으니까
if all([ri == bi, rj == bj]):
if rc > bc:
ri -= dx[i]
rj -= dy[i]
else:
bi -= dx[i]
bj -= dy[i]
# 방문 처리
if visited[ri][rj][bi][bj] == 0:
q.append([ri, rj, bi, bj, cnt + 1]) # 방문가능 경로 큐에 넣기
visited[ri][rj][bi][bj] = 1
# -1 예외 처리
print(-1)
# 알고리즘 백준 구슬탈출2 python
# 알고리즘 구슬 탈출2 파이썬 BJ13460
'✏️ 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺 > 백준 알고리즘' 카테고리의 다른 글
| [BJ3190] 뱀 (0) | 2022.04.28 |
|---|---|
| [BJ12100] 2048 (Easy) (0) | 2022.04.28 |
| [수학] [BJ2004] 조합 0의 개수 (0) | 2021.12.01 |
| [수학] [BJ1676] 팩토리얼 0의 개수 (0) | 2021.12.01 |
| [수학] [BJ10872] 팩토리얼 (0) | 2021.12.01 |