[백준/구현] 20057번: 마법사 상어와 토네이도(골드3, python)
https://www.acmicpc.net/problem/20057
20057번: 마법사 상어와 토네이도
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을
www.acmicpc.net
아이디어
구현해야 할 부분은 두 가지로 아래와 같았다.
1. 전체 맵을 반시계 방향으로 이동
2. 만약 이동한 곳에 모래가 있으면, 흩날리기~
# 1. 전체 맵을 반시계 방향으로 이동하기
반시계 방향으로 이동하기 위해서 방향 벡터를 사용하였다.
이렇게 정의해준 뒤, 방향 벡터 리스트 dv를 선언해주었다.
dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]
반시계 방향으로 탐색하는 방법은 아래와 같다.
1. 현재 위치에서 바라보는 방향만 반시계 방향으로 회전
2. 회전한 방향으로 전진
2-1. 만약 전진할 수 없으면 기존 방향으로 전진
2-1-1. 만약 기존 방향으로 전진할 수 없으면 마지막 인덱스이므로 종료
1~2 반복
2-1-1은 큐를 사용해서 구현했기 때문에 꼭 필요하지 않아 회색으로 표시 하였다.
구현하기 전 우선 시작 지점과 시작 방향을 설정해주었다.
x, y = N//2, N//2
d = 0가운데부터 시작하기 때문에 %2를 한 몫만 사용한다. 시작 방향은 위(0)이다.
while queue:
x, y, d = queue.popleft()
# 1. 시계 반대 방향으로 회전
nd = (d + 3) % 4
# 2. 회전한 방향으로 전진
nx = x + dv[nd][0]
ny = y + dv[nd][1]
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny, nd))
# 2-1. 회전한 방향으로 전진할 수 없으면 기존 방향으로 전진
elif nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny] == 1:
nx = x + dv[d][0]
ny = y + dv[d][1]
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny, d))
nd = d
else:
continue
#2. 모래 흩날리기
우선 이동한 곳에 모래가 없으면 다음 이동 위치로 넘어간다.
if board[nx][ny] == 0: continue
흩날리는 위치를 알려줄 벡터를 먼저 선언해주었다.
위 그림처럼 y를 기준으로 0~11까지의 방향을 정 하고(빨간 숫자) sv를 만들었다.
sv = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-2,0), (0,2), (2,0), (0,-2)]
그 후, s 리스트에 각각의 값을 담아주었다. (s의 n번째 인덱스의 값은 d가 n일때의 값이다.)
s는 흩날릴 위치(방향)를 담고있다.
이때 해당 위치에 모래의 몇 퍼센트가 날아가는지 모르기 때문에 퍼센트가 작은 곳의 위치부터 순서대로 담아주었다.
그리고 sp 리스트를 추가해서 각각의 퍼센트를 알려주었다.
# 1% -> 2% -> 5% -> 7% -> 10% -> a 순서
sp = [1, 1, 2, 2, 5, 7, 7, 10, 10, 0]
s = [[5, 3, 11, 9, 8, 6, 2, 7, 1, 0],
[7, 5, 8, 10, 9, 0, 4, 1, 3, 2],
[7, 1, 9, 11, 10, 6, 2, 5, 3, 4],
[1, 3, 8, 10, 11, 0, 4, 7, 5, 6]]
이후 흩날리는 모래를 계산해주면 된다.
# 3. 흩날리는 모래 계산
per = board[nx][ny] / 100
for idx, sd in enumerate(s[nd]):
sx = nx + sv[sd][0]
sy = ny + sv[sd][1]
if 0 <= sx < N and 0 <= sy < N:
if sp[idx] == 0: # 알파 자리라면
board[sx][sy] += board[nx][ny]
board[nx][ny] = 0
break
board[sx][sy] += int(per * sp[idx])
board[nx][ny] -= int(per * sp[idx])
continue
if sp[idx] == 0: # 알파 자리라면
answer += board[nx][ny]
board[nx][ny] = 0
break
answer += int(per * sp[idx])
board[nx][ny] -= int(per * sp[idx])알파 자리에서는 남은 값을 모두 보내고 nx, ny를 0으로 변경해준다.
전체 코드
from collections import deque
def bfs(x, y, d, N, board, visited):
dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]
sv = [(-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-2,0), (0,2), (2,0), (0,-2)]
# 1% -> 2% -> 5% -> 7% -> 10% -> a 순서
sp = [1, 1, 2, 2, 5, 7, 7, 10, 10, 0]
s = [[5, 3, 11, 9, 8, 6, 2, 7, 1, 0],
[7, 5, 8, 10, 9, 0, 4, 1, 3, 2],
[7, 1, 9, 11, 10, 6, 2, 5, 3, 4],
[1, 3, 8, 10, 11, 0, 4, 7, 5, 6]]
queue = deque([(x, y, d)])
visited[x][y] = 1
answer = 0
while queue:
x, y, d = queue.popleft()
# 1. 시계 반대 방향으로 회전
nd = (d + 3) % 4
# 2. 회전한 방향으로 전진
nx = x + dv[nd][0]
ny = y + dv[nd][1]
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny, nd))
# 2-1. 회전한 방향으로 전진할 수 없으면 기존 방향으로 전진
elif nx < 0 or nx >= N or ny < 0 or ny >= N or visited[nx][ny] == 1:
nx = x + dv[d][0]
ny = y + dv[d][1]
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
visited[nx][ny] = 1
queue.append((nx, ny, d))
nd = d
else:
continue
if board[nx][ny] == 0: continue
# 3. 흩날리는 모래 계산
per = board[nx][ny] / 100
for idx, sd in enumerate(s[nd]):
sx = nx + sv[sd][0]
sy = ny + sv[sd][1]
if 0 <= sx < N and 0 <= sy < N:
if sp[idx] == 0: # 알파 자리라면
board[sx][sy] += board[nx][ny]
board[nx][ny] = 0
break
board[sx][sy] += int(per * sp[idx])
board[nx][ny] -= int(per * sp[idx])
continue
if sp[idx] == 0: # 알파 자리라면
answer += board[nx][ny]
board[nx][ny] = 0
break
answer += int(per * sp[idx])
board[nx][ny] -= int(per * sp[idx])
return answer
N = int(input())
board = [[int(x) for x in input().split()] for _ in range(N)]
visited = [[0] * N for _ in range(N)]
# 시작점, 시작 방향
x, y = N//2, N//2
d = 0
print(bfs(x, y, d, N, board, visited))
