구슬 탈출 2
내 풀이
from collections import deque
n, m = map(int, input().split())
graph = []
red_ball, black_ball, target = (), (), ()
for i in range(n):
line = input()
row = list(line)
graph.append(row)
for l in range(len(graph)) :
for r in range(len(graph[0])) :
if graph[l][r] == "R" :
red_ball = (l, r)
if graph[l][r] == "B" :
black_ball = (l, r)
if graph[l][r] == "O" :
target = (l, r)
def can_pass(graph, r, c, flag):
if 0 <= r < n and 0 <= c < m :
return graph[r][c] != "#" and graph[r][c] != flag
class Route :
def __init__(self, graph, r_ball, b_ball, count) -> None:
self.graph = graph
self.r_ball = r_ball
self.b_ball = b_ball
self.count = count
def get_r_r(self) :
return self.r_ball[0]
def get_r_c(self) :
return self.r_ball[1]
def get_b_r(self) :
return self.b_ball[0]
def get_b_c(self) :
return self.b_ball[1]
def bfs(route: Route) :
dr = (1,-1,0,0)
dc = (0,0,-1,1)
graph = route.graph
q = deque()
q.append(route)
rr, rc = route.get_r_r(),route.get_r_c()
count = route.count
flag = 0
while q :
cur_route: Route = q.popleft()
for i in range(len(dr)) :
# 초기화
graph = cur_route.graph
rr, rc = cur_route.get_r_r(), route.get_r_c()
br, bc = cur_route.get_b_r(), route.get_b_c()
graph[rr][rc] = "."
graph[br][bc] = "."
r_ball, b_ball = cur_route.r_ball, cur_route.b_ball
count = cur_route.count
nrr = rr + dr[i]
nrc = rc + dc[i]
nbr = br + dr[i]
nbc = bc + dc[i]
can_pass_r = can_pass(graph=graph,r=nrr, c=nrc, flag="B")
can_pass_b = can_pass(graph=graph,r=nbr, c=nbc, flag="R")
if can_pass_r or can_pass_b :
# 벽에 부딛힐 때 까지 Red Ball 굴림
while can_pass_r :
rr = nrr
rc = nrc
if graph[rr][rc] == "O" :
flag += 1
nrr += dr[i]
nrc += dc[i]
can_pass_r = can_pass(graph=graph,r=nrr, c=nrc, flag="B")
# 벽에 부딪히기 전의 자리에 위치 저장
r_ball = (rr, rc)
graph[rr][rc] = "R"
# 벽에 부딛힐 때 까지 Red Ball 굴림
while can_pass_b :
br = nbr
bc = nbc
if graph[br][bc] == "O" :
flag += 1
nbr += dr[i]
nbc += dc[i]
can_pass_b = can_pass(graph=graph,r=nbr, c=nbc, flag="R")
# 벽에 부딪히기 전의 자리에 위치 저장
b_ball = (br, bc)
graph[br][bc] = "B"
count += 1
route = Route(graph=graph, r_ball=r_ball, b_ball=b_ball, count=count)
q.append(route)
if flag == 1 :
return route.count
if flag == 2 :
return -1
if count >= 10 :
return -1
return -1
route: Route = Route(graph=graph, r_ball=red_ball, b_ball=black_ball, count=0)
print(bfs(route=route))배운점
내 코드에서 문제가 됐던 점은 케이스는
5 8
########
#RB.##.#
##.#####
#.O..###
########
답 :: 2케이스와
6 7
#######
#..BR##
#.#####
#.#O###
#....##
#######
답 :: 8케이스이다.
사실상 문제에 나와있는 케이스는 다 맞췄는데 빨간색 공이 검은색 공에 막혀있어서 앞으로 나아가지 못하는 경우,
검은색 공이 먼저 혼자 들어가서 1이 나오는 경우를 계산하지 못하고 있다.
해설
2번 풀이
from sys import stdin
from collections import deque
input = stdin.readline
n, m = map(int, input().split())
board = [list(input().strip()) for _ in range(n)]
visited = [[[[False]*m for _ in range(n)] for _ in range(m)] for _ in range(n)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
q = deque()
def init():
rx, ry, bx, by = [0] * 4 # 초기화 0, 0, 0, 0
for i in range(n):
for j in range(m):
if board[i][j] == 'R': # board에 빨간 구슬이라면 좌표 값 저장
rx, ry = i, j
elif board[i][j] == 'B': # board에 파란 구슬이라면 좌표 값 저장
bx, by = i, j
q.append((rx, ry, bx, by, 1)) # 위치 정보와 depth
visited[rx][ry][bx][by] = True
def move(x, y, dx, dy):
count = 0 # 이동한 칸 수
# 다음 이동이 벽이거나 구멍이 아닐 때까지
while board[x+dx][y+dy] != '#' and board[x][y] != 'O':
x += dx
y += dy
count += 1
return x, y, count
def bfs():
init()
while q: # BFS -> queue, while
rx, ry, bx, by, depth = q.popleft() # FIFO
if depth > 10: # 10 이하여야 한다.
break
for i in range(len(dx)): # 4방향으로 시도한다.
next_rx, next_ry, r_count = move(rx, ry, dx[i], dy[i]) # RED
next_bx, next_by, b_count = move(bx, by, dx[i], dy[i]) # BLUE
if board[next_bx][next_by] == 'O': # 파란 구슬이 구멍에 떨어지지 않으면(실패 X)
continue
if board[next_rx][next_ry] == 'O': # 빨간 구슬이 구멍에 떨어진다면(성공)
print(depth)
return
if next_rx == next_bx and next_ry == next_by : # 빨간 구슬과 파란 구슬이 동시에 같은 칸에 있을 수 없다.
if r_count > b_count: # 이동 거리가 많은 구슬을 한칸 뒤로
next_rx -= dx[i]
next_ry -= dy[i]
else:
next_bx -= dx[i]
next_by -= dy[i]
# BFS 탐색을 마치고, 방문 여부 확인
if not visited[next_rx][next_ry][next_bx][next_by]:
visited[next_rx][next_ry][next_bx][next_by] = True
q.append((next_rx, next_ry, next_bx, next_by, depth +1))
print(-1) # 실패
bfs()1번 풀이
from collections import deque
import sys
input = sys.stdin.readline # 빠른 입출력 위한 코드
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input()))
for j in range(m):
if graph[i][j] == 'R': # 빨간구슬 위치
rx, ry = i, j
elif graph[i][j] == 'B': # 파란구슬 위치
bx, by = i, j
# 상 하 좌 우로 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
def bfs(rx, ry, bx, by):
q = deque()
q.append((rx, ry, bx, by))
visited = [] # 방문여부를 판단하기 위한 리스트
visited.append((rx, ry, bx, by))
count = 0
while q:
for _ in range(len(q)):
rx, ry, bx, by = q.popleft()
if count > 10: # 움직인 횟수가 10회 초과면 -1 출력
print(-1)
return
if graph[rx][ry] == 'O': # 현재 빨간 구슬의 위치가 구멍이라면 count출력
print(count)
return
for i in range(4): # 4방향 탐색
nrx, nry = rx, ry
while True: # #일 때까지 혹은 구멍일 때까지 움직임
nrx += dx[i]
nry += dy[i]
if graph[nrx][nry] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
nrx -= dx[i]
nry -= dy[i]
break
if graph[nrx][nry] == 'O':
break
nbx, nby = bx, by
while True: # #일 때까지 혹은 구멍일 때까지 움직임
nbx += dx[i]
nby += dy[i]
if graph[nbx][nby] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
nbx -= dx[i]
nby -= dy[i]
break
if graph[nbx][nby] == 'O':
break
if graph[nbx][nby] == 'O': # 파란구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안됨 따라서 이 경우 무시
continue
if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면
if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by): # 더 많이 이동한 구슬이 더 늦게 이동한 구슬이므로 늦게 이동한 구슬 한칸 뒤로 이동
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
if (nrx, nry, nbx, nby) not in visited: # 방문해본적이 없는 위치라면 새로 큐에 추가 후 방문 처리
q.append((nrx, nry, nbx, nby))
visited.append((nrx, nry, nbx, nby))
count += 1
print(-1) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우
bfs(rx, ry, bx, by)