[BOJ] 19237 - 어른 상어
문제링크
문제설명
1번부터 M번 사이의 번호가 붙은 상어 M마리가 N*N크가의 격자 상에 있다. 초기는 모든 상어가 자기 위치에 냄새를 뿌린다.
1초마다의 이동
- 모든 상어는 상하좌우 인접칸으로 이동하고 냄새를 뿌린다.
- 상어가 K번 이동하면 (k초뒤) 냄새는 사라진다.
- 이동 후 한칸에 여러 상어가 있으면 가장 번호가 작은 상어만 살아남는다 (1번이 제일 쎔)
이동 방향은 1 위, 2 아래, 3 왼쪽, 4 오른쪽으로 정의한다. 인접칸으로 이동하는 방향은
- 인접한 네 칸중 아무 냄새도 없는 칸
- 1번에 만족하는 칸이 없으면 내 냄새가 있는 칸
으로 이동한다. 만약 만족되는 칸이 여러개면, 입력으로 주어진 바라보는 방향 마다의 특정 우선 순위를 따른다.
상어의 머리 방향은 초기는 입력과 같이, 그 이후는 이동 방향이 보는 방향이다.
각 상어의 위치, 바라보는 방향, 그리고 상어마다의 이동 우선순위가 다음과 같이 입력으로 주어진다.
5 4 4 // N M k
0 0 0 0 3
0 2 0 0 0
1 0 0 0 4
0 0 0 0 0
0 0 0 0 0 // 격자위 상어들의 위치
4 4 3 1 // 상어들의 초기 바라보는 방향
2 3 1 4
4 1 2 3
3 4 2 1
4 3 1 2 // 상어 1의 상-하-좌-우 바라볼때의 이동 우선순위
2 4 3 1
2 1 3 4
3 4 1 2
4 1 2 3 // 상어 2의 상-하-좌-우 바라볼때의 이동 우선순위
4 3 2 1
1 4 3 2
1 3 2 4
3 2 1 4 // 상어 3의 상-하-좌-우 바라볼때의 이동 우선순위
3 4 1 2
3 2 4 1
1 4 2 3
1 4 2 3 // 상어 4의 상-하-좌-우 바라볼때의 이동 우선순위
이때 1번 상어만 남는데 걸리는 시간은?
문제 풀이
입력이 엄~~~청나게 길고 많아서 디버깅하기 어려울 것 같아 보였다,, 그래서 한방에 풀려고 수도코드를 최대한 자세히 써서 코드로 옮겼다.
입력받기
상어의 위치와 냄새는
smell[i][j]
: (i,j)칸 위의 [상어번호, 냄새의 남은시간]
shark[i][j]
: (i,j)칸 위에 있는 상어 번호 저장 -> 한칸에 여러 상어 있는지 검사용
shark[k]
: k번 상어가 d 방향 보고 (x,y)에 위치함을 [d, (x,y)]와 같이 저장하는 딕셔너리
와 같이 크게 세개의 리스트와 딕셔너리를 선언해서 저장했다.
각 상어마다 바라보는 방향에 따른 우선순위는 다음과 같이 저장했다.
priority[k][d]
: k번 상어가 방향 d를 바라볼때의 우선순위
smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
tmp = list(map(int, input().split()))
for j in range(N):
if tmp[j] != 0:
shark[i][j].append(tmp[j])
sharks[tmp[j]] = [(i,j)]
smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기
direction = list(map(int, input().split()))
for i in range(M):
sharks[i+1].append(direction[i])
priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
for j in range(4):
# i번 상어의 각 네방향 마다의 우선순위
priority[i+1].append(list(map(int, input().split())))
매 초마다의 이동
초마다의 이동은
- 우선 순위에 따라 인접 칸으로 상어 이동
for s in sharks.keys():
(x, y), d = sharks[s]
count_empty = [] # 빈칸 count
count_me = [] # 내 냄새가 있는 칸
# 4방향 검사하기
for i in range(1, 5):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny):
# 빈칸 count
if smell[nx][ny] == 0:
count_empty.append(i)
# 내 냄새가 있는 칸인지 count
elif smell[nx][ny][0] == s:
count_me.append(i)
if len(count_empty) == 1:
# 해당 칸으로 이동하기
shark[x][y].remove(s)
shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
elif len(count_empty) > 1:
# 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
for p in priority[s][d-1]:
if p in count_empty:
# 해당 방향으로 이동
shark[x][y].remove(s)
shark[x+dx[p]][y+dy[p]].append(s)
sharks[s] = [(x+dx[p],y+dy[p]), p]
break
elif len(count_me) == 1:
# 해당 칸으로 이동하기
shark[x][y].remove(s)
shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
elif len(count_me) > 1:
# 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
for p in priority[s][d-1]:
if p in count_me:
# 해당 방향으로 이동
shark[x][y].remove(s)
shark[x+dx[p]][y+dy[p]].append(s)
sharks[s] = [(x+dx[p],y+dy[p]), p]
break
겹치는 코드가 많아서 너무 길어진거같다... 겹치는 부분 따로 함수로 뺴면 더 깔끔할듯
- 한칸에 여러 상어 있는지 검사하고 내쫓기
: 2마리 이상 있는 칸에 대해서 오름차순으로 정렬하고, 제일 번호가 작은 상어 빼고 전부 내보낸다.
for i in range(N):
for j in range(N):
if len(shark[i][j]) > 1:
shark[i][j].sort()
# 제일 번호 작은 상어 빼고 다 내보내기
del_shark = shark[i][j][1:]
for s in del_shark:
(x, y), d = sharks[s]
shark[x][y].remove(s)
del(sharks[s])
n_shark -= 1
- 각 칸의 냄새에 대해 남은 시간 -= 1
for i in range(N):
for j in range(N):
if smell[i][j] != 0:
if smell[i][j][1] == 1:
smell[i][j] = 0
else:
smell[i][j][1] -= 1
- 이동한 칸에 대해서 냄새 뿌리기
for s in sharks.keys():
(x, y), d = sharks[s]
smell[x][y] = [s, K]
의 순서로 구현한다.
전체 코드
전체 코드는 다음과 같다.
import sys
from collections import deque, defaultdict
input = sys.stdin.readline
dx = [0, -1, 1, 0, 0] # 상1하2좌3우4
dy = [0, 0, 0, -1, 1]
N, M, K = map(int, input().split())
n_shark = M
def in_range(x, y):
if x in range(N) and y in range(N):
return True
return False
smell = [[0 for _ in range(N)] for _ in range(N)] # smell[i][j] = [상어번호, 남은시간]
shark = [[[] for _ in range(N)] for _ in range(N)] # shark[i][j] = [k] : (i,j)에 현재 k번 상어있음 -> 한칸에 여러 상어 있는지 검사용
sharks = {} # shark[k] = [d, (x,y)] : k번 상어가 d 방향 보고 (x,y)에 위치
for i in range(N):
tmp = list(map(int, input().split()))
for j in range(N):
if tmp[j] != 0:
shark[i][j].append(tmp[j])
sharks[tmp[j]] = [(i,j)]
smell[i][j] = [tmp[j], K] #초기 냄새, 시간 퍼뜨리기
direction = list(map(int, input().split()))
for i in range(M):
sharks[i+1].append(direction[i])
priority = defaultdict(list) # priority[k][d] : k번 상어의 방향 d 우선순위
for i in range(M):
for j in range(4):
# i번 상어의 각 네방향 마다의 우선순위
priority[i+1].append(list(map(int, input().split())))
time = 0
# 매초마다의 동작
while True:
if n_shark == 1:
print(time)
break
if time >= 1000:
print(-1)
break
# 모든 상어 이동
for s in sharks.keys():
(x, y), d = sharks[s]
count_empty = [] # 빈칸 count
count_me = [] # 내 냄새가 있는 칸
# 4방향 검사하기
for i in range(1, 5):
nx, ny = x+dx[i], y+dy[i]
if in_range(nx, ny):
# 빈칸 count
if smell[nx][ny] == 0:
count_empty.append(i)
# 내 냄새가 있는 칸인지 count
elif smell[nx][ny][0] == s:
count_me.append(i)
if len(count_empty) == 1:
# 해당 칸으로 이동하기
shark[x][y].remove(s)
shark[x+dx[count_empty[0]]][y+dy[count_empty[0]]].append(s)
sharks[s] = [(x+dx[count_empty[0]],y+dy[count_empty[0]]), count_empty[0]]
elif len(count_empty) > 1:
# 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
for p in priority[s][d-1]:
if p in count_empty:
# 해당 방향으로 이동
shark[x][y].remove(s)
shark[x+dx[p]][y+dy[p]].append(s)
sharks[s] = [(x+dx[p],y+dy[p]), p]
break
elif len(count_me) == 1:
# 해당 칸으로 이동하기
shark[x][y].remove(s)
shark[x+dx[count_me[0]]][y+dy[count_me[0]]].append(s)
sharks[s] = [(x+dx[count_me[0]],y+dy[count_me[0]]), count_me[0]]
elif len(count_me) > 1:
# 우선순위에 따라 이동하기 -> priority[k][d] : k번 상어의 d번 priority에 따라
for p in priority[s][d-1]:
if p in count_me:
# 해당 방향으로 이동
shark[x][y].remove(s)
shark[x+dx[p]][y+dy[p]].append(s)
sharks[s] = [(x+dx[p],y+dy[p]), p]
break
# 한칸에 여러 상어 있는지?
for i in range(N):
for j in range(N):
if len(shark[i][j]) > 1:
shark[i][j].sort()
# 제일 번호 작은 상어 빼고 다 내보내기
del_shark = shark[i][j][1:]
for s in del_shark:
(x, y), d = sharks[s]
shark[x][y].remove(s)
del(sharks[s])
n_shark -= 1
# 남은시간 -= 1
for i in range(N):
for j in range(N):
if smell[i][j] != 0:
if smell[i][j][1] == 1:
smell[i][j] = 0
else:
smell[i][j][1] -= 1
# 냄새 뿌리기
for s in sharks.keys():
(x, y), d = sharks[s]
smell[x][y] = [s, K]
time += 1
처음에 잘못 생각했던 부분이
1. 시간이 1000초이고 격자에 상어 1마리만 있을때
-> 이때는 1000이 정답이다.
2. 포문 돌면서 list 삭제,,,, 이건 매번 헷갈리느듯 ^_ㅠ
입력이 너무 길고 시뮬레이션 과정이 복잡해서 처음에 틀렸습니다 나와서 막막했는디.. 틀린 부분 빨리 찾아서 고쳤다 ^_^
소요시간
2시간 !
Author And Source
이 문제에 관하여([BOJ] 19237 - 어른 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-19237-어른-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)