https://www.acmicpc.net/problem/20057
백준 삼성 문제집에서 정답률이 가장 높은 문제(70.251%)
난이도는 골3 정도
달팽이 문제 연습용도로 좋음!
다른 상어문제 가기 전에 달팽이에 익숙해지는 용도로 다양한 방법으로 여러번 풀어보기
코드 설명1
1. 입력 받기
2. 토네이도 회전 구현
-> 무조건 왼쪽으로 회전하다가 이미 방문한 지점 나오면 직진
3. 비율 상하좌우로 구현
4. 토네이도 구현
※ 주의할 점
- 비율 소수점 버리기
- 토네이도 시작 점에는 모래가 남지 않음(0으로 초기화)
- 시작점 방문 체크 빼먹지 않기
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
# 3. 비율 상하좌우로 구현
left = [(0, -2, 0.05), (-1, -1, 0.1), (-1, 0, 0.07), (-1, 1, 0.01), (-2, 0, 0.02), (1, -1, 0.1), (1, 0, 0.07), (1, 1, 0.01), (2, 0, 0.02), (0, -1, 0)]
right = [(x, -y, d) for x, y, d in left]
up = [(y, -x, d) for x, y, d in left]
down = [(-y, x, d) for x, y, d in left]
dir = {0: left, 1: down, 2: right, 3: up}
# 4. 토네이도 구현
def move(sx, sy, d):
global ans
total = board[sx][sy]
sum = 0
for x, y, z in dir[d]:
nx = sx + x
ny = sy + y
if z == 0:
if nx >= N or nx < 0 or ny >= N or ny < 0:
ans += total - sum
else:
board[nx][ny] += (total - sum)
s = int(total * z)
sum += s
if nx >= N or nx < 0 or ny >= N or ny < 0:
ans += s
else:
board[nx][ny] += s
board[sx][sy] = 0
# 1. 입력 받기
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
ans = 0
d = -1
x, y = N//2, N//2
visited[x][y] = True
for i in range(N**2 - 1):
# 2. 토네이도 회전 구현
d = (d + 1) % 4
nx, ny = x + dx[d], y + dy[d]
if nx == N or nx == -1 or ny == N or ny == -1:
continue
if visited[nx][ny]:
d = (d - 1) % 4
nx, ny = x + dx[d], y + dy[d]
visited[nx][ny] = True
move(nx, ny, d)
x, y = nx, ny
print(ans)
코드 설명2
1. 입력 받기
2. 토네이도 회전 구현
-> 좌 - 하 - 우 - 상 방향이 몇 번씩 반복되는지
-> N * 2 - 1 번의 방향이 있고, 오른쪽 & 왼쪽으로 갈때마다 횟수가 한번씩 증가
-> 0 1 2 2 3 3 0 0 0 1 1 1 2 2 2 2 3 3 3 3
3. 비율 상하좌우로 구현
4. 토네이도 구현
※ 주의할 점
- 비율 소수점 버리기
- (안해도 되지만) 마지막에 왼쪽으로 한 번 더 가는 거 막아주기
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
# 3. 비율 상하좌우로 구현
left = [(0, -2, 0.05), (-1, -1, 0.1), (-1, 0, 0.07), (-1, 1, 0.01), (-2, 0, 0.02), (1, -1, 0.1), (1, 0, 0.07), (1, 1, 0.01), (2, 0, 0.02), (0, -1, 0)]
right = [(x, -y, d) for x, y, d in left]
up = [(y, -x, d) for x, y, d in left]
down = [(-y, x, d) for x, y, d in left]
dir = {0: left, 1: down, 2: right, 3: up}
# 4. 토네이도 구현
def move(sx, sy, d):
global ans
if sy < 0:
return
total = board[sx][sy]
sum = 0
for x, y, z in dir[d]:
nx = sx + x
ny = sy + y
if z == 0:
if nx >= N or nx < 0 or ny >= N or ny < 0:
ans += total - sum
else:
board[nx][ny] += (total - sum)
s = int(total * z)
sum += s
if nx >= N or nx < 0 or ny >= N or ny < 0:
ans += s
else:
board[nx][ny] += s
board[sx][sy] = 0
# 1. 입력 받기
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
ans = 0
x, y = N//2, N//2
time = 0
# 2. 토네이도 회전 구현
for i in range(N * 2 - 1):
d = i % 4
if d == 0 or d == 2:
time += 1
for _ in range(time):
nx = x + dx[d]
ny = y + dy[d]
move(nx, ny, d)
x, y = nx, ny
print(ans)
코드 결과
'백준 삼성' 카테고리의 다른 글
[python] 14888 - 연산자 끼워넣기 (0) | 2022.08.30 |
---|---|
[python] 17779 - 게리맨더링 2 (0) | 2022.08.29 |
[python] 19236 - 청소년 상어 (0) | 2022.08.27 |
[python] 23288 - 주사위 굴리기 2 (0) | 2022.08.26 |
[python] 14499 - 주사위 굴리기 (0) | 2022.08.26 |