19237 - 어른 상어

 

---

 

문제

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

19237번: 어른 상어

 

풀이

구현구현구현 문제다. 요구사항대로 구현하면 되긴하는데, 조건이 많고 섬세하게 구현해야해서 까다롭다.

 

나는 총 5개의 저장소를 활용했다. 

(1) 상어의 위치를 저장하는 2차원 배열

(2) 상어의 현재방향을 저장하는 1차원 배열

(3) 상어의 존재유무를 확인하는 set

(4) 상어의 냄새를 저장하는 2차원 배열

(5) 각 상어마다 우선순위 리스트가 저장되어있는 2차원 배열

 

그리고 (3)번인 set이 1이될때까지 함수를 반복적으로 돌렸다.

 

본격적인 풀이는 아래부터 설명한다.

 

 

상어의 움직임

 

상어는 1초만에 동시다발적으로 움직인다. 

그러나 코드에서는 그렇게 구현할 수 없기에, 원본 배열을 복사해준다.(상어 위치, 상어 냄새)

만약 이렇게 원본값을 복사하지 않고 사용하게 된다면 계속 갱신되는 배열값을 사용하게 되므로, 꼬이게 된다.

따라서 우리가 딱 이동하려는 그 순간의 배열을 복사해둬서 빈칸이나, 냄새의 정보들을 체킹하면 된다.

그리고 갱신 (상어 위치 변경, 냄새 감소)  은 원본배열에서 행하면 된다.

 

방향

 

우선적으로 빈칸이 있을경우 이동하게 된다. 만약 빈칸이 없으면 내 냄새를 향해서 이동하게 된다. 초기에 인접한 칸에 상어가 배치되지 않기에 이동할 수 없는 경우는 주어지지 않는다.

 

좀 말장난 같지만,  지문을 읽어보면 4방향 모두 체크해보고, 한개면 이동하고, 아니면 다른 로직을 블라블라.. 짜야 할거 같은 느낌이다. 그러나 그럴 필요 없이 우선순위 방향으로 바로 체크하면 된다. 어차피 빈칸이 한개면 우선순위 방향에서 돌다 걸릴테니 말이다. 만약 그렇게 다 돌았는데 빈칸이 없으면, 같은 방식으로 냄새를 찾으면 된다.

 

갱신

 

상어가 이동하게 된다면 갱신해줄것이 많다.

- 상어의 위치 (이전 위치는 0, 새로운 위치에 상어 번호)

- 상어가 바라보는 방향

- 상어의 냄새 (이동하자마자 퍼뜨리면 된다.)

 

기본적으로 이정도가 있고, 만약 이동할려는곳에 상어가 위치한다면

 '먹히는 상어의 존재 삭제' 를 추가적으로 처리하면 될 것이다.

 

갱신할때 순서를 주의해야한다, 앞에서 처리한 값이 뒤에 영향이 줄 수 있기 때문.

또한 위치같은 경우에 원본 배열을 복사해서 사용중이기에, '갱신배열 = 원본을 유지한 배열 값' 흐름을 잃으면 안된다.

'갱신배열' = '갱신배열' 해버리면 값이 꼬인다. 변수의 역할을 확실히 이해하고 코드 작성에 유의해야한다.

 

 

코드

import copy
from sys import stdin

def smellMinus():
    for i in range(n):
        for j in range(n):
            if smell[i][j][1] > 1:
                smell[i][j][1] -= 1
            elif smell[i][j][1] == 1:
                smell[i][j] = [0, 0]

def solution():
    global turn
    # 원본을 복사해둔다.
    t_area = copy.deepcopy(area)
    t_smell = copy.deepcopy(smell)

    # 냄새가 1 마이너스 된다.
    smellMinus()

    for i in range(n):
        for j in range(n):
            flag = False
            # 우리가 움직일 상어가 존재한다면
            if t_area[i][j] != 0:
                sharkNum = t_area[i][j] - 1
                x, y = i, j

                # 해당 상어가 바라보는 방향의 이동 우선순위
                search_list = p_dir[sharkNum][s_dir[sharkNum]-1]
                for val in search_list:
                    nx = x + dx[val]
                    ny = y + dy[val]
                    # 범위안에 들어가면서, 빈칸이면서, 냄새도 없는경우
                    if 0<=nx<n and 0<=ny<n:
                        if t_area[nx][ny] == 0 and t_smell[nx][ny][0] == 0:
                            flag = True
                            # 해당위치에 상어가 있을경우
                            if area[nx][ny] != 0:
                                # 내가 더 작은 상어일경우 -> 큰 상어 삭제 및 정보 갱신
                                if sharkNum+1 < area[nx][ny]:
                                    shark_set.remove(area[nx][ny])
                                    area[nx][ny] = t_area[x][y]
                                    area[x][y] = 0
                                    s_dir[sharkNum] = val
                                    smell[nx][ny] = [sharkNum+1, k]
                                    break

                                # 내가 더 크면 나를 삭제한다.
                                shark_set.remove(t_area[x][y])
                                area[x][y] = 0
                                break

                            # 상어가 없으면 이동해주고 바로 냄새를 뿌려주고, 정보갱신함
                            else:
                                area[nx][ny] = t_area[x][y]
                                area[x][y] = 0
                                smell[nx][ny] = [sharkNum+1, k]
                                s_dir[sharkNum] = val
                                break

                # 빈칸이 없는경우
                if not flag:
                    for val in search_list:
                        nx = x + dx[val]
                        ny = y + dy[val]
                        # 범위안에 들어가면서, 냄새가 내것인경우, 이동해주고 바로 냄새를 퍼트려준다.
                        if 0<=nx<n and 0<=ny<n:
                            if t_smell[nx][ny][0] == sharkNum+1:
                                smell[nx][ny] = [sharkNum+1, k]
                                area[nx][ny] = area[x][y]
                                area[x][y] = 0
                                s_dir[sharkNum] = val
                                break

    turn +=1

# empty, up, down, left, right -> idx는 1부터 시작.
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

n, m, k = map(int, stdin.readline().rstrip().split())
area = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
turn = 0

# s_dir -> 상어가 바라보는 방향을 저장한 배열
s_dir = list(map(int, stdin.readline().rstrip().split()))
# shark_set -> 현재 남아있는 상어들
shark_set = set()
for i in range(1, m+1): shark_set.add(i)

# smell -> 상어의 냄새를 저장
smell = [ [0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if area[i][j] != 0:
            smell[i][j] = [area[i][j], k]
        else:
            smell[i][j] = [0, 0]

# p_dir -> 상어의 우선순위 p_dir[0][1] -> 0번 상어가 아래쪽바라볼때 우선순위
# 단 상어는 1번부터 m번까지 존재, 조회시 -1해서 조회해야한다. (방향은 값 그대로 사용)
p_dir = [[0] * 4 for _ in range(m)]
for i in range(m):
    for j in range(4):
        p_dir[i][j] = list(map(int, stdin.readline().rstrip().split()))

while True:
    solution()
    if len(shark_set) == 1 or turn > 1000:
        break

print(turn) if turn <= 1000 else print(-1)

 

후기

 

삼성 문제들을 풀면서 점점 지문을 꼼꼼히 읽게 되었고, 요구사항 정리를 더욱 섬세하게 하게 되었다.

꼼꼼한 구현을 요구하는만큼, 초반 정리를 잘해두면 문제 풀이에 상당히 용이하다는것을 느끼고 있다.

그리고 디버깅할때도 그 흐름대로 잘 작성했는지 코드와 비교하면 비교적 빨리 오류를 찾아낼 수 있다.