[Python] 백준 13460: 구슬 탈출 2
https://www.acmicpc.net/problem/13460
풀이
- 4방향 모두 순회하면서 가능한 포지션과 움직인 횟수를 체크
- 한 번 기울일 때 파란 구슬이 빠지는 경우 바로 다음 방법으로 넘어가기
- 빨간 구슬이 구멍으로 빠지면 cnt 넘겨주기
- 이미 방문한 곳은 visited로 체크해서 중복 없게 하기
- 구슬 위치가 같아질 경우 이전 위치와 더 많이 차이나는 구슬을 뒤에 배치
코드
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
maps = []
r_position = [0, 0]
b_position = [0, 0]
for i in range(n):
temp = [x for x in input().rstrip()]
if 'R' in temp:
r_position = [temp.index('R'), i]
if 'B' in temp:
b_position = [temp.index('B'), i]
maps.append(temp)
#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append((cnt, r_position, b_position))
maps[r_position[1]import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
maps = []
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
temp = [x for x in input().rstrip()]
if 'R' in temp:
rx, ry = temp.index('R'), i
if 'B' in temp:
bx, by = temp.index('B'), i
maps.append(temp)
#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append([cnt, rx, ry, bx, by])
maps[ry][rx] = "."
maps[by][bx] = "."
visited = [[rx,ry,bx,by]]
def tilt():
while q:
cnt, rx, ry, bx, by = q.popleft()
for i in range(4):
r_nx, r_ny = rx, ry
b_nx, b_ny = bx, by
# 파란 구슬 이동
while maps[b_ny + dy[i]][b_nx + dx[i]] == ".":
b_nx += dx[i]
b_ny += dy[i]
# 파란 구슬이 빠질경우 다음 케이스로 넘어가기
if maps[b_ny + dy[i]][b_nx + dx[i]] == "O":
continue
# 빨간 구슬 이동
while maps[r_ny + dy[i]][r_nx + dx[i]] == ".":
r_nx += dx[i]
r_ny += dy[i]
if maps[r_ny + dy[i]][r_nx + dx[i]] == "O":
return cnt
else:
if r_nx == b_nx and r_ny == b_ny: # 같은 위치일 경우 더 많이 움직인 구슬을 뒤에
if abs(rx - r_nx) + abs(ry - r_ny) > abs(bx - b_nx) + abs(by - b_ny):
r_nx = r_nx - dx[i]
r_ny = r_ny - dy[i]
else:
b_nx = b_nx - dx[i]
b_ny = b_ny - dy[i]
if [r_nx, r_ny, b_nx, b_ny] not in visited:
q.append((cnt + 1, r_nx, r_ny, b_nx, b_ny))
visited.append([r_nx, r_ny, b_nx, b_ny])
if cnt > 10:
return -1
return -1
print(tilt())
import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
maps = []
r_position = [0, 0]
b_position = [0, 0]
for i in range(n):
temp = [x for x in input().rstrip()]
if 'R' in temp:
r_position = [temp.index('R'), i]
if 'B' in temp:
b_position = [temp.index('B'), i]
maps.append(temp)
#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append((cnt, r_position, b_position))
maps[r_position[1]import sys
input = sys.stdin.readline
from collections import deque
n, m = map(int, input().split())
maps = []
rx, ry, bx, by = 0, 0, 0, 0
for i in range(n):
temp = [x for x in input().rstrip()]
if 'R' in temp:
rx, ry = temp.index('R'), i
if 'B' in temp:
bx, by = temp.index('B'), i
maps.append(temp)
#0: 왼쪽, 1: 오른쪽, 2: 위, 3:아래
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cnt = 1
q = deque()
q.append([cnt, rx, ry, bx, by])
maps[ry][rx] = "."
maps[by][bx] = "."
visited = [[rx,ry,bx,by]]
def tilt():
while q:
cnt, rx, ry, bx, by = q.popleft()
for i in range(4):
r_nx, r_ny = rx, ry
b_nx, b_ny = bx, by
# 파란 구슬 이동
while maps[b_ny + dy[i]][b_nx + dx[i]] == ".":
b_nx += dx[i]
b_ny += dy[i]
# 파란 구슬이 빠질경우 다음 케이스로 넘어가기
if maps[b_ny + dy[i]][b_nx + dx[i]] == "O":
continue
# 빨간 구슬 이동
while maps[r_ny + dy[i]][r_nx + dx[i]] == ".":
r_nx += dx[i]
r_ny += dy[i]
if maps[r_ny + dy[i]][r_nx + dx[i]] == "O":
return cnt
else:
if r_nx == b_nx and r_ny == b_ny: # 같은 위치일 경우 더 많이 움직인 구슬을 뒤에
if abs(rx - r_nx) + abs(ry - r_ny) > abs(bx - b_nx) + abs(by - b_ny):
r_nx = r_nx - dx[i]
r_ny = r_ny - dy[i]
else:
b_nx = b_nx - dx[i]
b_ny = b_ny - dy[i]
if [r_nx, r_ny, b_nx, b_ny] not in visited:
q.append((cnt + 1, r_nx, r_ny, b_nx, b_ny))
visited.append([r_nx, r_ny, b_nx, b_ny])
if cnt > 10:
return -1
return -1
print(tilt())
질문에 있는 반례 다 넘어가는데 어디가 틀렸는지 모르겠다....ㅎ ㅏ..
3시간 넘게 걸려서 풀었는데 맞추지도 못하고 .. 착찹하다
부호를...>=
에서 >
로 바꾸니까 통과했다. 너무 허무하다..ㅠㅠ 정신차리자
Author And Source
이 문제에 관하여([Python] 백준 13460: 구슬 탈출 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@joniekwon/Python-백준-13460-구슬-탈출-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)