https://www.acmicpc.net/problem/13460
13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
문제 설명
위의 문제의 그림처럼 N * M 의 보드가 주어졌을 때, 빨간색 구슬을 구멍안에 넣는 게임이다.
파란색 구슬이 구멍안에 들어가서도 안되고,
굴리는 횟수가 10번을 넘어가서도 안된다.
여러가지 제약조건들이 많은 까다로운 BFS 문제이다.
풀이 과정
구슬을 굴리게 되면, 벽이나 구멍에 닿을 때 까지 구슬은 계속 굴러간다.
따라서, 방향 하나를 정했을 때 그 방향으로 계속 굴러가도록 while문을 통해 구슬을 굴려준다.
(코드의 roll함수의 while 부분)
또, 구슬이 굴러가다가 다른색의 구슬과 마주쳤을 경우에는
앞에 있는 구슬이 멈추면 내 구슬은 그 전칸에서 멈추게 되므로
각 구슬의 카운트를 통해 어떤 구슬이 앞에 있던 구슬인지 표기를 해준 후, 순서에 맞게 구슬을 배치하도록 한다.
또한, 4차원 visited 배열을 통해
발생했던 상황은 또 다시 발생하지 않도록 해준다.
2차원이 아닌 4차원 배열을 이용한 이유는
빨간색 구슬의 좌표는 이전과 같을지라도 파란색 구슬의 좌표가 다르다면 다른 상황이기 때문이다.
이를 파이썬 코드로 나타내면 다음과 같다.
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input()))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
def roll(x, y, direct):
cnt = 0
while graph[x + dx[direct]][y + dy[direct]] != '#' and graph[x][y] != 'O':
x += dx[direct]
y += dy[direct]
cnt += 1
return x, y, cnt
def bfs(ra, rb, ba, bb):
queue = deque()
queue.append((ra, rb, ba, bb, 1))
while queue:
rx, ry, bx, by, cnt = queue.popleft()
visited[rx][ry][bx][by] = True
if cnt > 10:
print(-1)
exit(0)
for i in range(4):
nrx, nry, rcnt = roll(rx, ry, i)
nbx, nby, bcnt = roll(bx, by, i)
if graph[nbx][nby] != 'O':
if graph[nrx][nry] == 'O':
print(cnt)
exit(0)
# 겹쳤을 때, 앞 뒤를 구분하여 재배치
if nrx == nbx and nry == nby:
if rcnt > bcnt:
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
if not visited[nrx][nry][nbx][nby]:
visited[nrx][nry][nbx][nby] = True
queue.append((nrx, nry, nbx, nby, cnt+1))
print(-1)
return
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
for j in range(m):
if graph[i][j] == 'R':
rx = i
ry = j
if graph[i][j] == 'B':
bx = i
by = j
bfs(rx, ry, bx, by)
ps. 실패 코드
이 코드는 방문했던 지점을 다시 방문하게 되면서 히든 케이스들을 통과하지 못한 코드이다.
참고용으로 첨부해놓았다.
from collections import deque
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input()))
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def redBall(x, y, direct):
nx = x + dx[direct]
ny = y + dy[direct]
while True:
if nx < 0 or nx >= n or ny < 0 or ny >= m:
break
if graph[nx][ny] == '#':
break
if graph[nx][ny] == 'O':
graph[x][y] = '.'
return -1, -1
if graph[nx][ny] == 'B':
bx, by = blueBall(nx, ny, direct)
if bx == nx and by == ny:
graph[x][y] = '.'
graph[nx-dx[direct]][ny - dy[direct]] = 'R'
return nx - dx[direct], ny - dy[direct]
if bx == -1 and by == -1:
print(-1)
exit(0)
nx = nx + dx[direct]
ny = ny + dy[direct]
graph[x][y] = '.'
graph[nx - dx[direct]][ny - dy[direct]] = 'R'
return nx - dx[direct], ny - dy[direct]
def blueBall(x, y, direct):
nx = x + dx[direct]
ny = y + dy[direct]
while True:
if nx < 0 or nx >= n or ny < 0 or ny >= m:
break
if graph[nx][ny] == '#':
break
if graph[nx][ny] == 'O':
return -1, -1
if graph[nx][ny] == 'R':
rx, ry = redBall(nx, ny, direct)
if rx == nx and ry == ny:
graph[x][y] = '.'
graph[nx - dx[direct]][ny - dy[direct]] = 'B'
return nx - dx[direct], ny - dy[direct]
nx = nx + dx[direct]
ny = ny + dy[direct]
graph[x][y] = '.'
graph[nx-dx[direct]][ny-dy[direct]] = 'B'
return nx - dx[direct], ny - dy[direct]
def bfs(ra, rb, ba, bb):
queue = deque()
queue.append((ra, rb, ba, bb, 1))
res = 1
while queue:
rx, ry, bx, by, cnt = queue.popleft()
if cnt > 10:
print(-1)
exit(0)
for i in range(4):
nrx, nry = redBall(rx, ry, i)
nbx, nby = blueBall(bx, by, i)
if nrx == -1 and nry == -1:
if nbx == -1 and nby == -1:
print(-1)
exit(0)
else:
print(cnt)
exit(0)
queue.append((nrx, nry, nbx, nby, cnt+1))
res = cnt
return res
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
for j in range(m):
if graph[i][j] == 'R':
rx = i
ry = j
if graph[i][j] == 'B':
bx = i
by = j
print(bfs(rx, ry, bx, by))전체 문제 & 코드는 위의 깃에 정리되어 있습니다.
팔로우 & 맞팔은 환영입니다 !
'Algorithm > DFS & BFS' 카테고리의 다른 글
| [백준] 14502 연구소 (Python 파이썬) (1) | 2021.10.17 |
|---|---|
| [백준] 12100 2048 (Easy) (Python 파이썬) (0) | 2021.10.14 |
| [프로그래머스] 거리두기 확인하기 (Python 파이썬) (0) | 2021.10.09 |
| [백준] 14888 연산자 끼워넣기 (Python 파이썬) (0) | 2021.10.08 |
| [백준] 2580 스도쿠 (Python 파이썬) (3) | 2021.10.08 |