[백준/19237] 어른 상어

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

19237번: 어른 상어

 최근 바빴던지라 문제풀이를 전혀 못했었는데, 오랜만에 한번 풀어봤습니다. 오랜만에 푼 게 삼성전자 공채 기출문제라니 쉽지는 않았으나.. 오히려 이전 청소년 상어보다 훨씬 쉽게 풀었습니다. 문제 조건 자체가 상당히 복잡하게 느껴졌는데, 이전에 한번 청소년 상어에서 호되게 당해서 그런지 몰라도 차근차근 구현하니까 풀만하게 느껴집니다.

---

 전형적인 구현(Implement) 문제이며, 작동방식이 '스네이크 게임'과 상당히 유사합니다. 특이한 점은 상어들이 각자 다른 이동패턴을 가지고 있다는 것입니다. 따라서 고려해야할 요소들이 조금 늘어나는 것 외에는 엄청 복잡한 문제는 아닙니다. 소스코드는 다음과 같습니다.

import copy

N, M, k = list(map(int, input().split()))
array = []
for _ in range(N):
    array.append(list(map(int, input().split())))
direction = list(map(int, input().split()))
pref = []
for i in range(M):
    tmp = []
    for _ in range(4):
        tmp.append(list(map(int, input().split())))
    pref.append(tmp)

time = [[[0, 0] for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if array[i][j] != 0:
            time[i][j][0] = array[i][j]
            time[i][j][1] = k

def find_shark(array, idx):
    for i in range(N):
        for j in range(N):
            if array[i][j] == idx:
                return i, j
    return None

def time_pass():
    for a in range(N):
        for b in range(N):
            if time[a][b][1] > 0:
                time[a][b][1] -= 1
                if time[a][b][1] == 0:
                    time[a][b][0] = 0

def next_location(x, y):
    for j in pref[array[x][y] - 1][direction[array[x][y] - 1] - 1]:
        nx, ny = x + dx[j - 1], y + dy[j - 1]
        if 0 <= nx < N and 0 <= ny < N:
            if time[nx][ny][0] == 0:
                return (nx, ny), j
            
    for j in pref[array[x][y] - 1][direction[array[x][y] - 1] - 1]:
        nx, ny = x + dx[j - 1], y + dy[j - 1]
        if 0 <= nx < N and 0 <= ny < N:
            if time[nx][ny][0] == time[x][y][0]:
                return (nx, ny), j      
    return None

def update(new_loc, new_direction, now):
    x, y = now
    nx, ny = new_loc
    direction[array[x][y] - 1] = new_direction
    array[nx][ny] = array[x][y]
    array[x][y] = 0
    time[nx][ny] = [array[nx][ny], k]
    
time = copy.deepcopy(time)
array = copy.deepcopy(array)
t = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(1000):
    prev = []
    for i in range(M):
        now = find_shark(array, i + 1)
        if now is not None:
            x, y = now
            new_loc, new_direction = next_location(x, y)
            if new_loc is not None:
                if new_loc not in [p[0] for p in prev]:
                    prev.append((new_loc, new_direction, now))
                else:
                    direction[array[x][y] - 1] = 0
                    array[x][y] = 0
    
    time_pass()
    for x, y, z in prev:
        update(x, y, z)
    t += 1
    
    if sum(direction[1:]) == 0:
        answer = t
        break
else:
    answer = -1

  크게 보면 입력을 받는 부분, 필요한 함수를 정의하는 부분, 그리고 정의한 함수를 활용하여 알고리즘을 수행하는 부분으로 나눌 수 있습니다.

---

입력을 받는 부분

N, M, k = list(map(int, input().split()))
array = []
for _ in range(N):
    array.append(list(map(int, input().split())))
direction = list(map(int, input().split()))
pref = []
for i in range(M):
    tmp = []
    for _ in range(4):
        tmp.append(list(map(int, input().split())))
    pref.append(tmp)

위와 같이 미리 N, M, k와 맵 정보, 방향 정보, 그리고 이동 패턴 정보(pref)를 모두 입력받아 저장하였습니다. 사실 초기화 과정에서 변수가 하나 더 필요한데, 바로 상어의 냄새가 남아있는 시간과 누구의 냄새인지 저장하는 변수입니다. 저는 time이라는 이름으로 초기화하였고, [상어 번호, 남은 시간] 형태로 저장하였습니다.

time = [[[0, 0] for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if array[i][j] != 0:
            time[i][j][0] = array[i][j]
            time[i][j][1] = k

 

---

함수를 정의하는 부분

 전체적인 흐름은 '상어별로 새로운 위치로 이동시켜 업데이트시킨 뒤, 시간을 센다'와 같이 진행됩니다. 따라서 이에 맞춘 기능의 함수를 정의하였습니다.

1) 상어 찾기

def find_shark(array, idx):
    for i in range(N):
        for j in range(N):
            if array[i][j] == idx:
                return i, j
    return None

 상어를 찾는 간단한 함수입니다. 전체 배열을 순회하며 인덱스에 해당하는 상어를 찾고, 찾으면 좌표를 반환하고 없으면 None을 반환합니다. 이전에 상어의 위치를 따로 배열을 만들어 관리하는 방법도 사용해봤으나(실제로 더 효율적이긴 합니다만) 문제는 오류 발생시 디버깅하기가 힘들어져서 관두었습니다. 실제로 구현 문제는 대부분 $O(N^{3})$ 이상의 시간복잡도로 구현해도 알고리즘만 문제없다면 정답 판정을 하는 것 같기도 하고요. 효율성 면에서는 힘을 뺐습니다.

 

2) 다음 위치 찾기

def next_location(x, y):
    for j in pref[array[x][y] - 1][direction[array[x][y] - 1] - 1]:
        nx, ny = x + dx[j - 1], y + dy[j - 1]
        if 0 <= nx < N and 0 <= ny < N:
            if time[nx][ny][0] == 0:
                return (nx, ny), j
            
    for j in pref[array[x][y] - 1][direction[array[x][y] - 1] - 1]:
        nx, ny = x + dx[j - 1], y + dy[j - 1]
        if 0 <= nx < N and 0 <= ny < N:
            if time[nx][ny][0] == time[x][y][0]:
                return (nx, ny), j      
    return None

 우선 기존에 초기화한 이동패턴 변수에서 현재 방향에 따른 선호하는 이동패턴을 가져옵니다. 이후 선호도 순으로 순회하며 이동가능한 경우가 존재하는지 찾습니다.

 중요한 점은, '우선 빈칸부터 찾고, 빈칸 중에 갈 수 있는 곳이 없으면 자신의 냄새가 나는 곳으로 간다'는 것입니다. 따라서 크게 두 파트로 나누어 구성했습니다. 위 부분은 빈칸 중에 갈 수 있는 경로가 있는 경우이고, 위에서 리턴되지 않는다면 아래 파트로 넘어갑니다. 아래 파트는 자신의 냄새가 나는 곳으로 돌아가는 경우입니다.

 상어는 언제나 자신이 왔던 길로 되돌아갈 수 있기 때문에, 갈 수 있는 길이 아예 없는 경우는 존재하지 않습니다. 그럼에도 혹시 몰라서 모든 경우가 안 걸리면 None을 반환하게는 해놓았습니다.

 

3) 맵 업데이트하기

def update(new_loc, new_direction, now):
    x, y = now
    nx, ny = new_loc
    direction[array[x][y] - 1] = new_direction
    array[nx][ny] = array[x][y]
    array[x][y] = 0
    time[nx][ny] = [array[nx][ny], k]

 필요한 정보는 현재 위치, 새로운 위치, 새로운 방향입니다. 이 정보들을 받아서 맵을 업데이트시킵니다. 이렇게 따로 구현한 이유는 '상어가 동시에 움직인다는 것'을 구현하기 위함입니다. 반복문을 이용하여 업데이트를 진행하면 상어가 동시에 이동한다는 조건에 맞지 않아서 오류가 발생합니다. 따라서 M마리 상어들의 이동 정보를 모두 하나의 변수에 담은 뒤, 최종적으로 업데이트를 진행하는 방식을 사용했습니다. 자세한 건 뒤에서 다시 언급하겠습니다.

 

4) 시간 계산

def time_pass():
    for a in range(N):
        for b in range(N):
            if time[a][b][1] > 0:
                time[a][b][1] -= 1
                if time[a][b][1] == 0:
                    time[a][b][0] = 0

 일정 시간 k가 지나면 상어가 남겨두었던 냄새가 사라진다고 했습니다. 따라서 매번 상어들의 이동이 끝날때마다 시간을 흐르게하여(남은 시간에서 1을 빼주어)야 합니다. time변수에 [상어 번호, 남은 시간]꼴로 저장하겠다고 했으므로, 남은 시간이 0이되면 상어 번호도 0으로 만듭니다.

 

알고리즘 수행

time = copy.deepcopy(time)
array = copy.deepcopy(array)
t = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(1000):
    prev = []
    for i in range(M):
        now = find_shark(array, i + 1)
        if now is not None:
            x, y = now
            new_loc, new_direction = next_location(x, y)
            if new_loc is not None:
                if new_loc not in [p[0] for p in prev]:
                    prev.append((new_loc, new_direction, now))
                else:
                    direction[array[x][y] - 1] = 0
                    array[x][y] = 0
    
    time_pass()
    for x, y, z in prev:
        update(x, y, z)
    t += 1
    
    if sum(direction[1:]) == 0:
        answer = t
        break
else:
    answer = -1

 본격적으로 알고리즘을 수행합니다. 이렇게 배열을 이용해서 정보를 순차적으로 업데이트하는 경우 깊은 복사를 해주는 것을 습관화해주는 것이 좋습니다. 생각보다 신경을 안 쓰면 잊기 쉬운 부분이고, 또 제가 겪었던 오류의 대부분은 여기서 기인했기 때문입니다. dx와 dy는 위, 아래, 왼쪽, 오른쪽 순서에 맞추어 초기화합니다.

 1000번 이내에 1번 상어만 남지 않는다면 -1을 반환하라고 했으므로 for문을 이용하여 1000번 반복시킵니다. prev 변수에 모든 상어들의 정보를 담을 예정입니다. 앞서 언급한대로 (상어가 존재한다면) 상어의 좌표를 구하고, 그 좌표를 토대로 다음에 이동할 좌표를 찾습니다. 이렇게 새로운 좌표를 찾고 나면 prev 변수에 같은 좌표가 들어있는지 확인합니다.

 prev 변수에 같은 좌표가 들었음을 확인하는 것은 상당히 중요합니다. 두 상어가 같은 좌표를 방문한다는 것은 한 상어가 사라진다는 것이고, 저는 낮은 번호의 상어부터 순차적으로 정보를 저장했습니다. 즉, 중복된 좌표를 반환한 상어는 무조건 맵에서 이탈하게 됩니다. 먼저 방문한 상어가 더 번호가 낮은(힘이 센) 상어일 것이기 때문입니다. 만약 중복된 좌표라면, 방향을 0으로 만들어주고 해당 좌표도 0으로 만들어 상어를 이탈시킵니다. 방향을 0으로 만들어준 것은 이후에 쓰입니다.

 그 후 시간을 먼저 흐르게 하는 것은(time_pass) 업데이트를 먼저 진행할 시 방금 이동한 위치의 냄새마저 카운팅되어버리기 때문입니다. 이전에 따로 prev변수를 입력으로 주어 예외처리하게 했었는데, 그것보다는 이게 더 깔끔한 것 같습니다. 시간이 흐른 뒤에는 앞서 만들었던 prev변수의 정보를 맵을 업데이트시킵니다.

 방향을 0으로 만든 것은 정답을 찾기 위해서였습니다. 만약 1번 상어 이외의 모든 상어가 맵에서 나갔다면 direction 변수의 0번 인덱스 외에 모든 인덱스가 0일 것입니다. 따라서 1번 인덱스부터 끝까지의 합이 모두 0이라면 해당 시점을 정답으로 반환하면 됩니다. 만약 1000번의 순회에도 정답이 나오지 않는다면, 제가 좋아하는 브레이크 체커를 이용하여 -1을 정답으로 하도록 하겠습니다.