문제
https://www.acmicpc.net/problem/16236
삼성문제이다
어제 새벽에 푼 문제인데 너무 늦어서 그냥 자고 오늘 올리게 되었다.
bfs로 풀었다
먼저 맵을 보면서 현재 상어 크기보다 작은 물고기가 1개라도 존재하는지 체크한다.
만약 없을경우 프로그램을 종료하고 있을경우 탐색을 시작하는 방법이다.
탐색의 경우 거리가 같을경우 위쪽, 왼쪽 물고기를 우선으로 먹는다는 조건이 있었는데, 어차피 bfs이므로 거리 순서대로 탐색할것이고, 탐색 순서를 위, 왼, 오, 아래로 설정하면 자동으로 그 조건에 맞게끔 탐색을 한다고 생각해서 자신보다 작은 물고기가 있으면 그냥 바로 먹게고 bfs 한 사이클 종료하게끔 처리했는데, 그렇게 짰더니 테스트케이스 1개가 틀렸다.
지나갈수 없는 벽의 존재 때문에 ( 자신보다 크기가 큰 물고기) 그렇게 처리하면 안되는 상황이 생긴다.
따라서 bfs를 돌면서 물고기를 바로 먹지말고, 탐색이 종료될때까지 거리와 좌표를 저장해두고 최종 탐색이 끝난 후, 후보들을 보면서 조건에 맞는 물고기를 골라 먹는식으로 짜야한다.
하나라도 찾으면 queue를 비우고 끝나게 처리했었는데 그래서 끝까지 다 돌면서 저장하게끔 바꾸었더니 성공했다.
거리와 좌표를 튜플로 배열에 담고, 배열을 lambda를 이용해 정렬해서 가장 가까우면서 위쪽, 왼쪽에 있는 순으로 정렬시켜 0번을 뽑았다.
근데 만약 이 배열이 비었을경우 답을 출력하고 프로그램 종료하는 처리도 해주어야 한다.
풀이
from collections import deque
dy = [-1,0,0,1]
dx = [0,-1,1,0]
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
size = 2
for i in range(n):
for j in range(n):
if arr[i][j] == 9:
current = (i,j)
break
answer = 0
exp = 0
while(1):
probList = []
for i in range(n):
for j in range(n):
if arr[i][j] < size and arr[i][j] != 0:
probList.append((i,j))
if len(probList) == 0 :
print(answer)
break
else :
check = [[0]*n for _ in range(n)]
q = deque()
q.append(current) # 현재좌표에서 bfs 시작
y,x = current
arr[y][x] = 0
check[y][x] = 1 # 초기거리 1부터시작, 나중에 -1해
q2 = deque()
temp = []
while(q):
y,x = q.popleft()
for i in range(4):
ny = y + dy[i]
nx = x + dx[i]
if 0 <= ny < n and 0 <= nx < n and check[ny][nx] == 0 and arr[ny][nx] <=size:
if arr[ny][nx] < size and arr[ny][nx] !=0 :
check[ny][nx] = check[y][x] + 1
temp.append(((ny,nx),check[y][x]))
else :
q.append((ny,nx))
check[ny][nx] = check[y][x] + 1
if len(temp) == 0:
print(answer)
break
temp.sort(key = lambda x: (x[1],x[0][0],x[0][1]))
current = temp[0][0]
y,x = current
exp += 1
if exp == size:
size += 1
exp = 0
arr[y][x] = 0
answer += temp[0][1]결과
jooooon