16236번 문제
BFS 탐색+구현 문제이다.
문제를 간략히 정리해보면
- 처음에 크기가 2인 아기상어가 있다. 이 아기상어는 1초마다 인접한 칸으로 이동이 가능하다.
- 아기상어는 자신과 크기가 같은 물고기는 지나갈 수 있고, 작은 물고기는 먹을 수 있다.
- 아기 상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다.
- 상어의 이동방식
- 가장 가까운 먹을 수 있는 물고기를 먹으러 간다.
- 가장 가까운 물고기가 복수라면, 가장 위의 물고기를 먹고, 가장 위의 물고기가 복수면 그중 가장 왼쪽의 물고기를 먹는다.
- 더 이상 먹을 물고기가 없으면, 끝난다.
여기까지가 문제의 정리였고, 이런 문제에서 상어의 탐색이 끝날때의 시간을 구하는 것이 요구사항이다.
이 문제를 처음 접했을 때 위의 '이동방식을 어떻게 구현할지', 그리고 '상어 크기는 어떻게 키울지' 두가지에 대한 구현법이 생각나지 않았다..
천천히 고민해보니, "가장 가까운 물고기가 복수라면, 가장 위의 물고기를 먹고, 가장 위의 물고기가 복수면 그중 가장 왼쪽의 물고기를 먹는다." 라는 구문은 물고기의 이동을 결정하는 dx,dy 리스트의 순서를 상, 좌, 우, 하 로 설정하면 되겠다고 생각했다.
이를 바탕으로 생각한 로직은
- 상어 위치를 좌표로 받는 BFS 탐색을 한다.
- 탐색 중 처음으로 만나는 물고기는 상어의 이동방식을 만족하는 물고기 이므로 먹는다.
- 물고기를 먹으면, 방문처리를 초기화 하고, 먹을때의 시간을 더해주고, 물고기의 크기를 조정한다.
- 이처럼 탐색이 다 끝나면, 원하는 시간이 나오고, 프로그램을 종료시킨다.
그렇게 처음 생각해낸 로직을 코드로 구현해보았다.
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
graph=[]
for _ in range(n):
graph.append(list(map(int, input().split())))
#아기 상어의 이동법(상, 좌, 우, 하)
dx=[-1,0,0,1]
dy=[0,-1,1,0]
def bfs(x,y):
visited=[[-1 for _ in range(n)]for _ in range(n)]
size=2
eat=0
time=0
q=deque()
q.append([x,y,0])
visited[x][y]=0
while q:
for _ in range(len(q)):
x,y,reset= q.popleft()
if reset==1:
q=deque()
q.append([x,y,0])
time=visited[x][y]
visited=[[-1 for _ in range(n)]for _ in range(n)]
visited[x][y]=time
break
if size==eat:
size+=1
eat=0
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n:
if visited[nx][ny]==-1:
if graph[nx][ny]==0 or graph[nx][ny]==size:
q.append([nx,ny,0])
visited[nx][ny]=visited[x][y]+1
elif 0<graph[nx][ny]<size:
eat+=1
reset=1
q.appendleft([nx,ny,reset])
visited[nx][ny]=visited[x][y]+1
graph[nx][ny]=0
break
return time
for i in range(n):
for j in range(n):
if graph[i][j]==9:
graph[i][j]=0
ans=bfs(i,j)
print(ans)
exit()문제에 주어진 예시를 돌리다가 다른 것들은 잘 나오는데 4번째 예시에서 틀리게 나왔다..
그렇다. dx=[-1,0,0,1], dy=[0,-1,1,0] 를 이용한 이동방식은 아래와 같은 예시가 있을때 정상작동하지 못하게 된다.
5
0 0 9 0 1
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0이 경우 위의 코드로 돌리면 처음으로 만나는 물고기의 위치는 (1,1)이다. 하지만 거리가 같은 상태에서 가장 위의 물고기를 먹어야 하므로 (0,4)의 물고기를 먹는 것이 맞다.
즉, BFS 탐색시 방향 우선순위로 해결할 수 없다.
그럼 어떻게 해야 문제를 풀수 있을까?
문제 핵심
- 이 문제는 현재 상태에서 상어가 잡아먹을 수 있는 모든 물고기를 조사한 다음에 가장 거리가 짧고 위에 있고, 왼쪽인 물고기를 찾아야 한다.
- 완전 탐색을 통해서 먹을 물고기의 위치를 정하는 것이다.
로직을 다시 세워보자.
- 상어 위치를 좌표로 받는 BFS 탐색을 한다.(기존 그래프의 상어 위치는 0으로 변경해준다.(향후 통과하기 위해))
- 탐색 중 본인보다 크기가 작은 물고기는 별도의 리스트에 (시간,x,y)로 담아준다. 빈칸이거나 본인과 크기가 같은 물고기는 지나간다.
- 탐색이 끝나면, 조건문을 통해 리스트가 비어있다면 false를, 아니면 리스트를 (시간, x좌표, y좌표) 순으로 정렬한다.
- 상어 크기를 조정해주고, 시간을 더해주고 상어가 더이상 먹을 고기가 없을때 까지 반복해준다.
그럼 이 로직을 코드로 작성해보자.
import sys
input=sys.stdin.readline
from collections import deque
n=int(input())
graph=[]
for _ in range(n):
graph.append(list(map(int, input().split())))
#이동방식에 대해서는 아무렇게나 설정해도 된다.
dx=[-1,0,0,1]
dy=[0,-1,1,0]
def bfs(time,x,y):
visited=[[0 for _ in range(n)]for _ in range(n)]
eat_lst=[]
q=deque()
q.append([time,x,y])
visited[x][y]=1
while q:
time,x,y= q.popleft()
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if 0<=nx<n and 0<=ny<n and visited[nx][ny]==0:
if graph[nx][ny]==0 or graph[nx][ny]==size:
q.append([time+1,nx,ny])
visited[nx][ny]=1
elif 0<graph[nx][ny]<size:
eat_lst.append([time+1,nx,ny])
visited[nx][ny]=1
#리스트가 비었을 때
if len(eat_lst)==0:
return False
#아니라면 sorted 정렬을 한다.
else:
return sorted(eat_lst)
for i in range(n):
for j in range(n):
if graph[i][j]==9:
x=i
y=j
size=2
eat=0
time=0
while 1:
graph[x][y]=0
ans=bfs(0,x,y)
#탐색에서 False 를 반환하면, 더이상 먹을게 없으므로 break
if ans==False:
print(time)
break
eat+=1
if size==eat:
size+=1
eat=0
x=ans[0][1]
y=ans[0][2]
time+=ans[0][0]
사실 이 문제에서 제일 중요한 것은 정렬이다.
필자는 이 문제를 풀때 정렬에 대해서 생각을 못하고 풀었다.. (그래서 빙빙 돌아갔다..ㅜ)
sorted 정렬은 기본적으로 앞에 있는 인자를 우선순위로 정렬한다.
따라서 굳이 람다 정렬을 사용할 필요는 없다.(위의 코드처럼 리스트 구성을 (시간, x좌표, y좌표)로 구성한다면 필요없는 것이다.)
아닐 경우 람다정렬을 사용해주면 된다.
람다 정렬의 경우 아래의 링크에 잘 정리되어 있다.
출처: https://bang-tori.tistory.com/5
이번 문제는 구현이 어려웠던 문제였다..
역시 코딩은 막힐때 다른 방식으로 전환해보는 사고의 전환이 중요한것 같다.
