[G3] 16236 아기 상어

유형: 구현 + 그래프 탐색

문제 푸는데 1시간, 한줄 오류 때문에 반례 찾다가 1시간 지남

• 구현같은 복잡한 코드에서는 예외처리, if 케이스 구분 확실히 해야 하는듯
• if문 안에 and로 조건 여러개 묶이는게 보기 불편해서
  a 조건이랑 b조건은 이거로 퉁쳐도 되겠지?
  - 했다가 그거때문에 1시간 날림
• 코드 좀 길어지더라도 꼼꼼히 반례 찾자

→ 디버깅하다 알게된 점은, 무한루프도 시간초과로 뜨기 때문에 생각해볼 여지가 있다

풀이 시간 : 2시간

제출 코드

from collections import deque

N = int(input())
def isValid(x, y):
    return 0<=x<N and 0<=y<N

table = []
for _ in range(N):
    table.append(list(map(int, input().split())))
# print(table)

dist = 0
baby_size = 2
req_sizeup = 2
# 상어 위치 찾기
start_x, start_y = -1,-1
for i in range(N):
    if start_x != -1 and start_y != -1:
        break
    for j in range(N):
        if table[i][j] == 9:
            start_y = i
            start_x = j
            break
            
while True:
    # 탐색
    distances = [[-1 for _ in range(N)] for _ in range(N)]
    distances[start_y][start_x] = 0
    reachable = [] # 물고기 잡아먹는 case (거리, y, x)
    stack = deque([(start_y, start_x)])
    while stack:
        curr_y, curr_x = stack.popleft()

        # 물고기 찾은 상태에서 해당 dist 보다 큰 경우 탐색 안 함
        if reachable and reachable[-1][0] < distances[curr_y][curr_x]:
            break

        # 해당 노드에 먹을 수 있는 물고기가 있는지 확인
        if table[curr_y][curr_x] != 0 and table[curr_y][curr_x] != 9 and table[curr_y][curr_x] < baby_size:
            reachable.append((distances[curr_y][curr_x], curr_y, curr_x))
        else: # 
            dy = [1, 0, 0, -1]
            dx = [0, -1, 1, 0]
            for k in range(4):
                new_x = curr_x+dx[k]
                new_y = curr_y+dy[k]
                
                # 다음 노드 추가
                if isValid(new_x, new_y) and table[new_y][new_x] <= baby_size and distances[new_y][new_x] == -1:
                    stack.append((new_y, new_x))
                    distances[new_y][new_x] = distances[curr_y][curr_x]+1
        # print('end of loop: ', stack)
    # print(reachable)
    if not reachable:
        break

    # 물고기 잡아먹기 테이블에 적
    res_dist, res_y, res_x = sorted(reachable)[0]
    # print(res_dist, res_y, res_x)
    dist += res_dist
    table[start_y][start_x] = 0
    table[res_y][res_x] = 9
    req_sizeup -= 1
    if req_sizeup == 0:
        baby_size += 1
        req_sizeup = baby_size
    # 상어 위치 업데이트
    start_y = res_y
    start_x = res_x
print(dist)