[221004] 백준 19327 : 어른 상어

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

19237번: 어른 상어

1. 딕셔너리의 적극적인 활용

 상어의 위치를 계속해서 추적해줘야 하는데, 좌표 정보를 어떻게 업데이트할 것인가 고민을 많이 했다.

기존에 자주 하던 방식은 리스트에 [번호, x, y]값을 지정해서 추가시켜주는 것이었는데, 이번에는 뭔가 번호 한 번 검색하면 바로바로 뜨게 함으로써 인덱싱 및 좌표 값 수정하는 데 있어서 구구절절 코딩하고 싶지 않았다. 그래서 딕셔너리를 사용했다. 각 상어에 따른 이동 규칙도 딕셔너리로 만들어 주었다. 예제 1번에서의 1번 상어의 딕셔너리 정보는 다음과 같이 정리할 수 있다.

아쉬운 부분은, 이동규칙에 따른 리스트를 추출할 때에는 빈 배열이 들어가 있지 않아서 1을 빼줘야만 했다. 위의 그림에서는 바라보는 방향 인덱스 번호가 0~3으로 지정되어있기 때문이다. 할 수는 있는데, 이 정도는 머릿속으로 해결 가능하겠다 싶어서 안 함. 물론 좋은 코딩 습관은 아니다. 남들이 보면 대환 장할 수준의 레거시 코드가 될 수 있기 때문이다. 역량테스트를 위한 시험문제풀이이니 적당히 넘어가도록 하자. 하지만 현실 코딩에서는 그러면 안 됨.

2. 상어 냄새 묻히기와 시간 추가, 그리고 이동하기

 이 문제의 주의할 점은 바로 상어의 위치를 추적하는 것이다. 코드 내용상 순서가 살짝 뒤바뀌는 것만으로도 오답 판정을 받는다. 그만큼 반복문 안에서 조건들을 잘 이행해주는 것이 중요하다. 해당 문제에서는

 

"상어가 냄새를 묻히고"

"1초 뒤"

"상어가 이동한다"

 

라고 되어있다. 

이대로 정확하게 진행해줘야 한다. 상어가 이동하면서 냄새 묻히고 없애고 한 번에 구현하려고 했다가는 반례 폭격 바로 맞아버린다. 따라서 난 여기에 대한 흐름도를 다음과 같이 구상했다.

 

3. 전체 코드

 메모리 : 116252 KB, 시간 : 228 ms, 풀이 시간 : 75 min

N, M, k = map(int, input().split())
board = [[[0, 0] for _ in range(N)] for _ in range(N)] # 상어 번호, 상어 냄새
s_coord = {}
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] != 0 :
            s_coord[tmp[j]] = [i, j]
d_info = list(map(int, input().split()))
d_spec = {}
for i in range(M):
    temp = []
    for _ in range(4):
        temp.append(list(map(int, input().split())))
    d_spec[i+1] = temp
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

def solve():
    time = 0
    while True :
        check_cnt = 0
        for i in range(M):
            if s_coord[i + 1] : # 있는 경우에만 배치
                x, y = s_coord[i + 1]
                if board[x][y][0] != i + 1 and board[x][y][1] == k : # 중복 위치
                    num1, num2 = board[x][y][0], i + 1
                    board[x][y][0] = min(board[x][y][0], i + 1)
                    if num1 < num2 : s_coord[num2] = []
                    else : s_coord[num1] = []
                    check_cnt += 1
                else : board[x][y][0] = i + 1
                board[x][y][1] = k
            else :
                check_cnt += 1
        if M - check_cnt == 1 : break
        if time > 1000 : break
        time += 1
        for i in range(M): # Move
            if s_coord[i + 1] :
                x, y = s_coord[i + 1]
                d_temp = d_spec[i+1][d_info[i]-1] # 이동 규칙 배열
                # 최초 이동 실시
                # 인접한 곳 중 빈 곳 먼저 가자
                cnt = 0
                for d in range(4) :
                    nx = x + dx[d_temp[d]]
                    ny = y + dy[d_temp[d]]
                    if 0 <= nx < N and 0 <= ny < N and board[nx][ny][1] == 0 :
                        s_coord[i + 1] = [nx, ny]
                        # 방향도 바꿔줘야함
                        d_info[i] = d_temp[d]
                        break
                    else : cnt += 1
                if cnt < 4 :
                    continue
                else :
                    for d in range(4):
                        nx = x + dx[d_temp[d]]
                        ny = y + dy[d_temp[d]]
                        if 0 <= nx < N and 0 <= ny < N and board[nx][ny][0] == i + 1 :
                            s_coord[i + 1] = [nx, ny]
                            d_info[i] = d_temp[d]
                            break
        for i in range(N):
            for j in range(N):
                if board[i][j][1] > 0 :
                    board[i][j][1] = max(board[i][j][1] - 1, 0)
                    if board[i][j][1] == 0 :
                        board[i][j][0] = 0
    return time
result = solve()
if result > 1000 :
    print(-1)
else :
    print(result)