[백준 19237번] 어른상어(파이썬)

https://www.acmicpc.net/problem/19237

19237번: 어른 상어

이 문제는
구현하는 것도 어려운 편인데
상어의 위치나
냄새 등등을
어떻게 저장하는가도 어려웠습니다.
이 문제를 풀면서
좀 어렵다고 느끼긴 했지만
파이썬의 리스트활용에 대해서
많이 공부를 할 수 있었죠.

이 문제를 풀 때에는
deepcopy를 많이 이용했습니다.
이 문제가 구현이 힘든 이유는
'상어가 동시에 이동한다'
'이동 후에 냄새가 지워진다'
라는 걸 어떻게 구현하는지
좀처럼 생각하기 힘들기 떄문입니다.

제가 막혔던 케이스를
그림으로 그려봤습니다.
제가 생각하기에는
위의 케이스가
의외로 고려하기 힘들었을 거라고 생각합니다.
저는 이를 위해서
deep copy로
smell과 water를 복사하고
그 다음에 상어 이동을 실시했습니다.

코드를 보시겠습니다.

#백준 19237 어른상어
import copy

N,M,K=map(int,input().split())

water=[list(map(int,input().split())) for _ in range(N)]

t_distance=list(map(int,input().split()))

distance=[[[],[]]for _ in range(M)]
smell=[[[0,0]for _ in range(N)] for _ in range(N)] #distance에 각 물고기의 좌표랑 방향 넣어주기
for fish in range(1,M+1):
for x in range(N):
    next=0
for y in range(N):
if water[x][y]==fish:
    smell[x][y][0]=fish
    smell[x][y][1]=K
distance[fish-1][0].append([x,y])
next=1
break
if next==1:
break

for i in range(M):
distance[i][1].append(t_distance[i])
#print(distance)
#각 상어의 방향에 따른 우선순위 받음
priority=[[[],[],[],[]]for _ in range(M)]
for m in range(M):
for d in range(4):
priority[m][d]=list(map(int,input().split()))
#print(priority)
#print(priority[0])
#print(priority[0][0])
#인접한 칸 보기
dx=[0,-1,1,0,0]
dy=[0,0,0,-1,1] time=1 while time<=1000:
#print(time)
#print() tmp_water=[]
tmp_water=copy.deepcopy(water)
tmp_smell=[]
tmp_smell=copy.deepcopy(smell)

#1.인접한 칸 중 아무냄새 없는 칸을 방향으로 잡는다
for fish in range(1,M+1): #print(1)
#이미 빠저나간 물고기는 빼고 계산
if len(distance[fish-1])==0:
continue
x,y=distance[fish-1][0][0]
d=distance[fish-1][1][0]
#print(x,y,d)
em=0
#print(priority[fish-1][d-1])
for nd in priority[fish-1][d-1]:
nx=x+dx[nd]
ny=y+dy[nd] if nx<0 or nx>=N or ny<0 or ny>=N:
continue

if not water[nx][ny] and not smell[nx][ny][0]:
#동시에 이동해야하므로, 임시저장한 tmp_water와 비교한다
#water에서는 빈칸인데 tmp_water에서는 이동했다면 이동 취소
if not tmp_water[nx][ny]:
tmp_water[nx][ny]=tmp_water[x][y]
tmp_water[x][y]=0
distance[fish-1][0][0]=nx,ny
distance[fish-1][1][0]=nd
tmp_smell[nx][ny][0]=fish
tmp_smell[nx][ny][1]=K+1
em=1
break
else:
#앞선 상어가 먼저 이동했다는 경우
tmp_water[x][y]=0
distance[fish-1].clear()
em=1
break
if em==1:
#print("do 1")
continue
#print("do2")
#print(priority[fish-1][d-1])
#2. 자신의 냄새가 있는 칸
for nd in priority[fish-1][d-1]:
nx=x+dx[nd]
ny=y+dy[nd]
if nx<0 or nx>=N or ny<0 or ny>=N:
#print("do")
continue
if smell[nx][ny][0]==fish:
tmp_water[nx][ny]=tmp_water[x][y]
tmp_water[x][y]=0
distance[fish-1][0][0]=nx,ny
distance[fish-1][1][0]=nd
tmp_smell[nx][ny][0]=fish
tmp_smell[nx][ny][1]=K+1
#print("out")
#print(nd)
break
#냄새빼주기
for x in range(N):
for y in range(N):
if tmp_smell[x][y][1]:
tmp_smell[x][y][1]-=1
if not tmp_smell[x][y][1]:
tmp_smell[x][y][0]=0

water=copy.deepcopy(tmp_water)
smell=copy.deepcopy(tmp_smell)
#길이판별 후 종료
len_d=0
for i in range(M):
if distance[i]:
len_d+=1
if len_d==1:
break
time+=1
"""
print(len_d)
print()
print(water)
print()
print(smell)
print()
print(distance)
print()
print(len(distance))
print()
"""
if time>1000:
    print(-1)
else:
    print(time)

저는 디버깅을 위해
예시1이 14라는 점을 활용해서
time을 15까지로 제한시킨 후에
출력해서 디버깅을 실시했습니다.
저는 다소 어렵게 돌아간 느낌이 강한데
인터넷의 솔루션들보니
저보다 간결한 느낌...
사서 고생한 느낌 ㅋㅋ
어찌되었든 공부많은 공부는 했다만...ㅎㅎ

 

 

+++++

 

#19237번 어른상어

N,M,K=map(int,input().split())


dx=[-1,1,0,0]
dy=[0,0,-1,1]


shark=[[]]*(M+1)
s_distance=[0]
d_priority=[[[],[],[],[]]for _ in range(M+1)]

graph=[]
smell=[[[0,0]for _ in range(N)]for _ in range(N)]
for i in range(N):
    data=list(map(int,input().split()))
    for j in range(N):
        if data[j]:
            shark[data[j]]=[i,j]
            smell[i][j]=[data[j],K]
    graph.append(data)
data=list(map(int,input().split()))
for i in range(M):
    data[i]-=1
s_distance+=data


for i in range(1,M+1):
    for j in range(4):
        a,b,c,d=map(int,input().split())
        d_priority[i][j]=[a-1,b-1,c-1,d-1]
time=1
while time<=1000:
    #상어를 순서대로 뻄
    for s in range(1,M+1):
        if not shark[s]:
            continue
        sx,sy=shark[s]
        s_d=s_distance[s]
        n_priority=d_priority[s][s_d]
        #우선순위대로 이동한다
        #먼저 냄새없는 칸을 보면 이동하는 걸로
        flag=0

        for d in n_priority:
            nx=sx+dx[d]
            ny=sy+dy[d]

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if smell[nx][ny]==[0,0]:
                flag=1
                #아무것도 없을 경우
                if graph[nx][ny]==0:
                    graph[nx][ny],graph[sx][sy]=graph[sx][sy],graph[nx][ny]
                    shark[s]=[nx,ny]
                    s_distance[s]=d
                #이동한 칸에 다른 물고기가 있을 경우
                #1 이동하는 곳이 더 우선순위(더 작은 경우)
                elif graph[nx][ny]<s and not graph[nx][ny]==0:
                    graph[sx][sy]=0
                    shark[s]=[]
                #2. 현재가 더 우선순위(현재가 더 작음)
                elif graph[nx][ny]>graph[sx][sy] and not graph[nx][ny]==0:
                    shark[graph[nx][ny]]=[]
                    graph[nx][ny]=s
                    s_distance[s]=d
                break
        if flag==1:
            continue

        #자신의 냄새칸을 본다.
        flag = 0
        for d in n_priority:
            nx = sx + dx[d]
            ny = sy + dy[d]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if smell[nx][ny][0] == s:
                graph[nx][ny], graph[sx][sy] = graph[sx][sy], graph[nx][ny]
                shark[s] = [nx, ny]
                s_distance[s] = d
                flag = 1
                break
        if flag == 1:
            continue
    #현재 이동한 거에 넘새 남겨주기
    for s in range(1,M+1):
        if not shark[s]:
            continue
        sx,sy=shark[s]
        smell[sx][sy]=[s,K+1]
    #전에 냄새 하나씩 뺴주기
    for x in range(N):
        for y in range(N):
            if smell[x][y][1]>0:
                smell[x][y][1]-=1
                if smell[x][y][1]==0:
                    smell[x][y]=[0,0]
    flag=0
    for s in range(2,M+1):
        if shark[s]:
            flag=1
            break
    if flag==0:
        break
    time+=1
if time>1000:
    print(-1)
else:
    print(time)

바뀐 버전입니다.

 

개선점

1. 굳이 deepcopy를 안 써도 된다.

문제의 조건은 냄새의 여부로 움직이기 때문.

 

'temp안쓰면 이동한 칸에 다른 상어가 오는 건

어떻게 구현할 건가요?'

라는 질문이 오실 수 있습니다.

우선, 같은 냄새칸을 이동하는 경우는

크게 신경안써도 됩니다.

자기 냄새가 있는 칸으로만 이동하니

다른 상어가 있을 수가 없습니다.

상어1의 냄새라면

상어1만 들어갈 수 있기 때문에

다른 상어2,3,4...등 등은 신경쓸 이유가 없습니다.

그리고 자기 냄새가 있는 구역이라면

'계속 비어있는 상황'이므로

그냥 옮겨주면 됩니다.

 

그리고 상어를 번호순대로 이동시킨다고 가정했습니다.

만약에 둘이 겹친다.

그럼 우선순위가 높은 녀석이 이깁니다.

자연스럽게 아닌 친구는 빼주면 됩니다.

 

*문제 풀다가 유의할 부분

 

1.

저는 여기서 nx,ny의 위치와 sx,sy의 위치를 변경하는 식으로

코드를 작성했습니다.

그런데 엄밀하게 보자면

graph[nx][ny]=graph[sx][sy]

graph[sx][sy]=0

이렇게 하는 것이 맞습니다.

서로 자리를 바꿔주는 것이 아닌

sx,sy의 것이

nx,ny위치로 가는 것이기 때문입니다.

문제 특성상 sx,sy가 어처피 비어서 다행이지만

fm대로라면 이동하는 것으로 표현해야 합니다.

 

2.

맞왜틀을 유발하게 만든 조건입니다.

저는 처음에

time=0으로 세팅하고

while<1000으로 두고 풀었습니다.

그러다 25%에서 계속 틀렸습니다 라고 떴습니다.

확인해본 결과,

제 코드상에서는 1000번째가 999로 되는데

이렇게 되면 time이 1000일 때는 10001번 수행한 게 되버려서

time=1000이 -1로 떴습니다.

되게 사소한 부분인데

저런 부분 하나 때문에

한참을 해메었습니다.

문제에서 출력조건을 놓치면

이렇게 삥 돌아가실 수 있으니

조건은 조심하고 또 조심!

 

https://chldkato.tistory.com/183

백준 19237 어른 상어 (파이썬)

https://velog.io/@koyo/boj-19237

[백준- 19237] 어른상어

https://jjangsungwon.tistory.com/55

[ 백준 19237 ] 어른 상어 - Python