[BOJ] 16236 아기상어 python

 

삼성 서류에 붙었으니만큼, 코테를 확실히 준비하는 것이 맞지 않나싶어 열심히 풀어보고 있다.

 

작년 하반기에는 메모리 분석 및 평가 포지션에 넣었는데 광탈했던 슬픈 기억이 새록새록 ㅎㅎ...

from collections import deque
N = int(input())
pool = [] #전체적인 지도
for i in range (0,N):
    a = list(map(int,input().split()))
    for j in range (0,len(a)):
        if a[j] == 9:
            start = [i,j]
    pool.append(a)

ans,exp,lev = 0,0,2 #exp가 lev와 같아지면 lev += 1, exp = 0
dx,dy = [0,0,1,-1], [1,-1,0,0]

def bfs(x,y):
    visited = [[0 for _ in range (0,N)] for _ in range (0,N)]
    deq = deque([[x,y]])
    next = []
    visited[x][y] = 1
    while deq:
        t = deq.popleft()
        a,b = t[0], t[1]
        for i in range (0,4):
            aa,bb = a + dx[i], b + dy[i]
            if 0 <= aa < N and 0 <= bb < N and visited[aa][bb] == 0:
                if pool[x][y] > pool[aa][bb] and pool[aa][bb] != 0:
                    visited[aa][bb] = visited[a][b] + 1
                    next.append([visited[aa][bb]-1, aa,bb])
                elif pool[aa][bb] == pool[x][y]:
                    visited[aa][bb] = visited[a][b] + 1
                    deq.append([aa,bb])
                elif pool[aa][bb] == 0:
                    visited[aa][bb] = visited[a][b] + 1
                    deq.append([aa,bb])
    next.sort(key = lambda x: (x[0], x[1], x[2]))
    pool[x][y] = 0
    if next == []:
        return None
    return next[0]

while True:
    pool[start[0]][start[1]] = lev
    t = bfs(start[0], start[1])
    if t == None:
        break
    else:
        ans += t[0]
        exp += 1
        start = [t[1], t[2]]
        if lev == exp:
            exp = 0
            lev += 1
        pool[start[0]][start[1]] = 0
print(ans)

 

BFS를 최대한 잘 사용하는 것이 좋을 것 같다.

삼성 코딩 테스트까지 얼마 남지 않았는데, 잘 준비해서 좋은 결과 있었으면 좋겠다.

 

제발 오전에 봤으면 좋겠다 ... (오후부터 LG전자 코테 예정되어있음)