[백준 19237번] 어른 상어 문제 풀이

< 문제 >

 

 

 

 

 

< 입출력 >

 

 

 

 

< 풀이 >

(1) 배열에 상어 번호와 냄새가 남은 시간을 저장 - arr 배열

다음과 같이 초기 배열이 정해지면 아래처럼 배열에 [상어 번호, 냄새가 남은 시간] 으로 저장한다. 

[

[[0, 0], [0, 0], [0, 0], [0, 0], [3, 4]], 

[[0, 0], [2, 4], [0, 0], [0, 0], [0, 0]],

[[1, 4], [0, 0], [0, 0], [0, 0], [4, 4]],

[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0]],

[[0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]

]

 

(2) 각 상어의 현재 위치 저장  - location 배열
[[], [2, 0], [1, 1], [0, 4], [2, 4]]

→ 각 상어의 위치 인덱스를 저장해준다

 

 

(3) 각 상어의 현재 방향을 저장 - direction 배열

[[0, 4, 4, 3, 1] - 1번부터 M번 상어의 현재 방향을 저장하고, 0번 인덱스에는 임의로 0을 넣어준다.

 

 

(4) 각 상어의 우선 순위 방향을 저장 - favorite 배열

[[], 

[[2, 3, 1, 4], [4, 1, 2, 3], [3, 4, 2, 1], [4, 3, 1, 2]], 

[[2, 4, 3, 1], [2, 1, 3, 4], [3, 4, 1, 2], [4, 1, 2, 3]], 

[[4, 3, 2, 1], [1, 4, 3, 2], [1, 3, 2, 4], [3, 2, 1, 4]], 

[[3, 4, 1, 2], [3, 2, 4, 1], [1, 4, 2, 3], [1, 4, 2, 3]]

]

 

 

 

< 코드 >

import sys
input = sys.stdin.readline


N, M, k = map(int, input().split())
arr = []            # 칸에 몇번 상어가 있는지 기록
location = [[] for i in range(M+1)]    # 상어의 현재 위치 기록
smell = []           # 남아 있는 냄새 인덱스 기록
count = M          # 남은 상어의 개수
dead_shark =[]

for i in range(N):
    t = list(map(int, input().split()))
    group = []
    for j in range(N):
        shark = t[j]
        if shark != 0:                # 상어의 현재 위치 배열에 넣어 주기
            location[shark].append(i)
            location[shark].append(j)
            smell.append([i, j])
            group.append([shark, k])   # 방향과 초기 시간 k도 넣어줌
        else:
            group.append([shark, 0])
    arr.append(group)

direction = [0]
for i in list(map(int, input().split())):
    direction.append(i)     # 초기 방향 저장
favorite = [[] for _ in range(M+1)]
for i in range(1, M + 1):
    for j in range(4):
        favorite[i].append(list(map(int, input().split())))

total_time =0

while total_time <= 1000:
    decision_direction = [0 for i in range(M+1)]                # 각 상어의 이동 방향 결정된 것을 저장
    decision_location = [[] for i in range(M+1)]                 # 각 상어의 이동 위치 결정된 것을 저장

    for shark in range(1, M+1):                # 1번부터 M번 상어 이동 위치 판단
        decision = 0                       # 이동 위치 정했는 지 여부
        if shark in dead_shark:
            continue
        d = direction[shark]                   # 각 상어의 현재 방향
        a = location[shark][0]                    # 각 상어의 현재 위치
        b = location[shark][1]
        for j in favorite[shark][d-1]:           # 우선 순위 부터 하나씩 인접한 칸 중 아무 냄새가 없는 칸이 있는지
            if j == 1:                     # 우선 순위가 1번이면
                if a > 0 and arr[a-1][b][0] == 0:
                    decision = 1
                    decision_direction[shark] = 1
                    decision_location[shark] = [a - 1, b]
                    break

            elif j == 2:                   # 우선 순위가 2번이면
                if a < N-1 and arr[a+1][b][0] == 0:
                    decision = 1
                    decision_direction[shark] = 2
                    decision_location[shark] =[a + 1, b]
                    break

            elif j == 3:                   # 우선 순위가 3번이면
                if b > 0 and arr[a][b-1][0] == 0:
                    decision = 1
                    decision_direction[shark] = 3
                    decision_location[shark] =[a, b-1]
                    break
            else:
                if b < N-1 and arr[a][b+1][0] == 0:
                    decision = 1
                    decision_direction[shark] = 4
                    decision_location[shark] =[a, b+1]
                    break

        if decision == 0:   # 인접한 칸 중 아무 냄새가 없는 곳이 없는 경우
            for j in favorite[shark][d - 1]:
                if j == 1:
                    if a > 0 and arr[a - 1][b][0] == shark:
                        decision = 1
                        decision_direction[shark] = 1
                        decision_location[shark] = [a - 1, b]
                        break

                elif j == 2:  # 우선 순위가 2번이면
                    if a < N - 1 and arr[a + 1][b][0] == shark:
                        decision = 1
                        decision_direction[shark] = 2
                        decision_location[shark] =[a + 1, b]
                        break

                elif j == 3:  # 우선 순위가 3번이면
                    if b > 0 and arr[a][b - 1][0] == shark:
                        decision = 1
                        decision_direction[shark] = 3
                        decision_location[shark] = [a, b - 1]
                        break
                else:
                    if b < N - 1 and arr[a][b + 1][0] == shark:
                        decision = 1
                        decision_direction[shark] = 4
                        decision_location[shark] = [a, b + 1]
                        break
    total_time +=1

    for i in range(1, M):
        for j in range(i+1, M+1):
            if i not in dead_shark and j not in dead_shark:
                if decision_location[i]== decision_location[j]:

                    dead_shark.append(j)
                    decision_location[j] = []
                    decision_direction[j] = 0
                    count -= 1

    print("decision_location = ",decision_location)
    print("decision_direction =", decision_direction)
    if count == 1:
        print(total_time)
        exit()

    temp = []
    for s in smell:
        x = s[0]
        y = s[1]
        arr[x][y][1] -= 1
        if arr[x][y][1] == 0:   # 냄새 시간이 0이 되면
            arr[x][y][0] = 0
        if arr[x][y][1] > 0:
            temp.append(s)
    smell = temp
    print("arr=", arr)
    print("smell=", smell)

    for i in range(1, M+1):
        if i not in dead_shark:
            new_x = decision_location[i][0]
            new_y = decision_location[i][1]
            arr[new_x][new_y][0] = i
            arr[new_x][new_y][1] = k
            smell.append([new_x, new_y])
    direction = decision_direction
    location = decision_location


print(-1)