[백준] 19237번 어른 상어
문제 링크
https://www.acmicpc.net/problem/19237
문제 설명
- 상어들이 냄새를 풍기면서 돌아다님
- 냄새가 없거나 자신의 냄새가 있거나.. 등 우선순위에 따라
- 겹치면 숫자 작은 상어가 쫓아냄
- 1만 남았을 경우 종료
풀이
- board, 현재 위치, 현재 방향, 냄새를 따로 관리
- 매 초마다
- 체크
- 이동
- 쫓아내기
- 냄새 갱신
코드
def move():
for num in range(1, m+1):
y, x = shark[num]
if not (0 <= y < n) or not (0 <= x <n):
continue
positions = get_nothing(num, y, x, dirs[num])
if not positions:
positions = get_mine(num, y, x, dirs[num])
if not positions:
continue
ny, nx, nd = positions[0]
board[ny][nx].append(board[y][x].pop())
dirs[num] = nd
shark[num] = (ny, nx)
def get_mine(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][0] == num:
positions.append([ny, nx, nd])
return positions
def get_nothing(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][1] == 0:
positions.append([ny, nx, nd])
return positions
def out():
for y in range(n):
for x in range(n):
if len(board[y][x]) >= 2:
minn = min(board[y][x])
for num in board[y][x]:
if num != minn:
shark[num] = (-1, -1)
board[y][x] = [minn]
def spread():
for y in range(n):
for x in range(n):
if smell[y][x][1] > 0:
smell[y][x][1] -= 1
if smell[y][x][1] == 0:
smell[y][x][0] = 0
if board[y][x]:
smell[y][x] = [board[y][x][0], k]
# init
import sys
read = sys.stdin.readline
n,m,k = map(int,read().split())
board = [[[] for _ in range(n)] for _ in range(n)]
smell = [[[0,0] for _ in range(n)] for _ in range(n)]
shark = [(-1, -1) for _ in range(m+1)]
for i in range(n):
line = list(map(int, read().split()))
for j in range(n):
if line[j] > 0:
shark[line[j]] = (i, j)
board[i][j].append(line[j])
smell[i][j] = [line[j], k]
dirs = [0] + list(map(int, read().split()))
priority = [[]]
for _ in range(m):
tmp = [[]]
for _ in range(4):
tmp.append(list(map(int, read().split())))
priority.append(tmp)
dy, dx = [0,-1,1,0,0], [0,0,0,-1,1]
# start
answer = -1
for t in range(1001):
if len(set(shark)) == 2:
answer = t
break
move()
out()
spread()
print(answer)
Author And Source
이 문제에 관하여([백준] 19237번 어른 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-19237번-어른-상어
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- board, 현재 위치, 현재 방향, 냄새를 따로 관리
- 매 초마다
- 체크
- 이동
- 쫓아내기
- 냄새 갱신
코드
def move():
for num in range(1, m+1):
y, x = shark[num]
if not (0 <= y < n) or not (0 <= x <n):
continue
positions = get_nothing(num, y, x, dirs[num])
if not positions:
positions = get_mine(num, y, x, dirs[num])
if not positions:
continue
ny, nx, nd = positions[0]
board[ny][nx].append(board[y][x].pop())
dirs[num] = nd
shark[num] = (ny, nx)
def get_mine(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][0] == num:
positions.append([ny, nx, nd])
return positions
def get_nothing(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][1] == 0:
positions.append([ny, nx, nd])
return positions
def out():
for y in range(n):
for x in range(n):
if len(board[y][x]) >= 2:
minn = min(board[y][x])
for num in board[y][x]:
if num != minn:
shark[num] = (-1, -1)
board[y][x] = [minn]
def spread():
for y in range(n):
for x in range(n):
if smell[y][x][1] > 0:
smell[y][x][1] -= 1
if smell[y][x][1] == 0:
smell[y][x][0] = 0
if board[y][x]:
smell[y][x] = [board[y][x][0], k]
# init
import sys
read = sys.stdin.readline
n,m,k = map(int,read().split())
board = [[[] for _ in range(n)] for _ in range(n)]
smell = [[[0,0] for _ in range(n)] for _ in range(n)]
shark = [(-1, -1) for _ in range(m+1)]
for i in range(n):
line = list(map(int, read().split()))
for j in range(n):
if line[j] > 0:
shark[line[j]] = (i, j)
board[i][j].append(line[j])
smell[i][j] = [line[j], k]
dirs = [0] + list(map(int, read().split()))
priority = [[]]
for _ in range(m):
tmp = [[]]
for _ in range(4):
tmp.append(list(map(int, read().split())))
priority.append(tmp)
dy, dx = [0,-1,1,0,0], [0,0,0,-1,1]
# start
answer = -1
for t in range(1001):
if len(set(shark)) == 2:
answer = t
break
move()
out()
spread()
print(answer)
Author And Source
이 문제에 관하여([백준] 19237번 어른 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-19237번-어른-상어
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def move():
for num in range(1, m+1):
y, x = shark[num]
if not (0 <= y < n) or not (0 <= x <n):
continue
positions = get_nothing(num, y, x, dirs[num])
if not positions:
positions = get_mine(num, y, x, dirs[num])
if not positions:
continue
ny, nx, nd = positions[0]
board[ny][nx].append(board[y][x].pop())
dirs[num] = nd
shark[num] = (ny, nx)
def get_mine(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][0] == num:
positions.append([ny, nx, nd])
return positions
def get_nothing(num, y, x, d):
positions = []
for nd in priority[num][d]:
ny, nx = y + dy[nd], x + dx[nd]
if 0 <= ny < n and 0 <= nx < n:
if smell[ny][nx][1] == 0:
positions.append([ny, nx, nd])
return positions
def out():
for y in range(n):
for x in range(n):
if len(board[y][x]) >= 2:
minn = min(board[y][x])
for num in board[y][x]:
if num != minn:
shark[num] = (-1, -1)
board[y][x] = [minn]
def spread():
for y in range(n):
for x in range(n):
if smell[y][x][1] > 0:
smell[y][x][1] -= 1
if smell[y][x][1] == 0:
smell[y][x][0] = 0
if board[y][x]:
smell[y][x] = [board[y][x][0], k]
# init
import sys
read = sys.stdin.readline
n,m,k = map(int,read().split())
board = [[[] for _ in range(n)] for _ in range(n)]
smell = [[[0,0] for _ in range(n)] for _ in range(n)]
shark = [(-1, -1) for _ in range(m+1)]
for i in range(n):
line = list(map(int, read().split()))
for j in range(n):
if line[j] > 0:
shark[line[j]] = (i, j)
board[i][j].append(line[j])
smell[i][j] = [line[j], k]
dirs = [0] + list(map(int, read().split()))
priority = [[]]
for _ in range(m):
tmp = [[]]
for _ in range(4):
tmp.append(list(map(int, read().split())))
priority.append(tmp)
dy, dx = [0,-1,1,0,0], [0,0,0,-1,1]
# start
answer = -1
for t in range(1001):
if len(set(shark)) == 2:
answer = t
break
move()
out()
spread()
print(answer)
Author And Source
이 문제에 관하여([백준] 19237번 어른 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-19237번-어른-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)