[Python] n19237번 | 어른 상어

문제 출처 : www.acmicpc.net/problem/19237

상어 번호 : 1~M이하의 자연수 번호, 랜덤 (단, 모든 번호는 다르다)

가장 강력한 상어 : 1의 번호를 가진 상어

격자 크기 : N X N

상어가 들어있는 칸의 개수 : M

 

1단계 (이동)

- 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다.

- 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 하나로 이동하고, 자신의 냄새를 그 칸에 뿌린다.

(냄새는 상어가 K번 이동하고 나면 사라진다)

 

이동 방향 결정 방법

1순위 ) 인접한 칸 중 아무 냄새가 없는 칸의 방향을 잡는다

2순위 ) 그런 칸이 없으면 자신의 냄새가 있는 칸의 방향으로 잡는다.

(이때 가능한 칸이 여러개 일 수 있는데, 이땐 특정한 우선순위를 따라야 한다.)

우선순위는 상어마다 다를 수 있고, 같은 상어라도 바라보고 있는 방향에 따라 다를 수 있다.

상어가 맨 처음에 보고 있는 방향은 입력으로 주어지고, 그 후에는 방금 이동한 방향이 보고 있는 방향이 된다.

 

2단계 (모든 상어가 이동한 후)

한 칸에 여러 마리의 상어가 남아있으면, 가장 작은 번호를 가진 상어를 제외하고 모두 격자밖으로 쫓겨난다.

그림1

 

상어 왼쪽 상단에 있는 정수는 상어의 번호 또는 냄새를 뿌린 상어의 번호이다.

왼쪽 하단에 있는 정수는 냄새를 의미하고, 그 값은 사라지기까지 남은 시간이다. 

 

 

 

상어 1을 예시로 들어보기!

상어 1의 머리가 오른쪽 방향으로 향해있으니까 

오른쪽 방향의 우선순위를 확인하기.

우선순위는 오른쪽 > 왼쪽 > 위쪽 > 아래쪽이다.

오른쪽 칸에 아무 냄새가 없으면 이동할 수 있다.

그러나 오른쪽에 냄새가 있으면 왼쪽칸을 확인하고,

상하좌우에 있는 인접한 칸들에 아무 냄새가 없는 칸이 없으면,

이제 자신의 냄새가 있는 칸을 찾는다.

 

1번 상어만 격자에 남게 될때까지 몇 초가 걸리는지를 구하라

단,

맨 처음에는 각 상어마다 인접한 빈 칸이 존재해서 이동을 못 하는 경우는 없다.

1000초가 넘어도 다른 상어가 격자에 남아있으면 -1을 출력한다.

 

---

* 주의사항 *

1.

무조건 정보를 한 리스트에 담으려고 하지말고,

냄새랑 상어 번호는 smell 리스트에,

상어 위치정보는 Map 리스트에,

현재 상어들의 방향은 directions 리스트에 넣어서

덜 복잡하게 관리를 할 수 있다.

 

2.

예외상황, 격자를 벗어난다던가,

현재 있는 위치에 냄새가 퍼져있는 상태라던가,

이런 상황들을 초기에 발견해야 오류가 발생하지 않는다.

 

3.

냄새 정보가 없는 칸을 찾는 for문을 돌리다가,

결국 찾지 못 했을 땐 

자신의 냄새가 있는 칸을 찾아야한다.

found라는 bool 변수를 통해서,

전자 for문에서 칸을 찾았는지 안 찾았는지 판별하고,

만약 칸을 찾지 못했다면

자신의 냄새가 있는 칸을 찾는 for문으로 넘어간다.

반대로 냄새 정보가 없는 칸이 있다면?

그때는 continue문을 통해 위로 올라간다.

왜냐면 아래 for문을 돌릴 필요가 없기 때문이다.

 

4. 

1번 상어만 있는지 확인할 때도

bool 변수를 사용하면 편리하다.

만약 1번 상어말고 다른 상어가 존재하면,

변수의 값을 false로 바꾼다.

그리고 아래 if문에서, 

그 값이 true이면 1번 상어만 존재하는 거니까, 

while 무한 루프를 빠져나오고, time을 출력한다.

 

만약 false값이면,

반복문을 빠져나올 수 없다.

아래 남아있는 단계를 계속 진행한다

 

# N : 격자크기, M : 상어가 들어있는 칸의 개수, K : 냄새 지속시간
N, M, K = map(int, input().split())

# 격자 (Map은 2차원 배열)
Map = [list(map(int, input().split())) for _ in range(N)]

# 현재 상어들의 방향 #1,2,3,4번 상어 순
directions = list(map(int, input().split()))

# 상어들의 우선순위
shark_priority = [[] for _ in range(M)]
for i in range(M):
    for j in range(4):
        shark_priority[i].append(list(map(int, input().split())))

# 냄새는 또 다른 리스트에 담기, 크기는 Map 크기와 동일
# 냄새리스트[상어 번호, 냄새 지속타임]
# for는 [] 자체를 복사, * N 은 내용만 복사
smell = [[[0, 0] for _ in range(N)] for _ in range(N)]

# 상, 하 , 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
time = 0

while True:
    # 모든 상어가 자신의 위치에 냄새를 뿌린다.
    for i in range(N):
        for j in range(N):
            if smell[i][j][1] > 0:
                smell[i][j][1] -= 1
            if Map[i][j] != 0:
                smell[i][j] = [Map[i][j], K]

    # 그 후에 1초마다 모든 상어가 이동하고 자신의 냄새를 그 칸에 뿌린다.

    temp = [[0 for _ in range(N)] for _ in range(N)]

    # 아무 냄새가 없는 칸을 찾는 과정
    for x in range(N):
        for y in range(N):
            if Map[x][y]:
                now_dir = directions[Map[x][y] - 1]
                we_found = False
                for z in range(4):
                    nx = x + dx[shark_priority[Map[x][y] - 1][now_dir - 1][z] - 1]
                    ny = y + dy[shark_priority[Map[x][y] - 1][now_dir - 1][z] - 1]
                    if nx >= 0 and nx < N and ny >= 0 and ny < N:
                        if smell[nx][ny][1] == 0:  # 아무 냄새가 없을 경우
                            directions[Map[x][y] - 1] = shark_priority[Map[x][y] - 1][now_dir - 1][z]
                            if temp[nx][ny] == 0:
                                temp[nx][ny] = Map[x][y]
                            else:
                                temp[nx][ny] = min(temp[nx][ny], Map[x][y])
                            we_found = True
                            break

                # 위에서 칸을 찾았는지 안 찾았는지 체크하는 단계
                if we_found:
                    continue

                # 모든 칸에 냄새가 차 있어서 위에서 움직이지 못했을 경우, 이제 자신의 냄새가 있는 칸을 찾는다.
                for index in range(4):
                    nx = x + dx[shark_priority[Map[x][y] - 1][now_dir - 1][index] - 1]
                    ny = y + dy[shark_priority[Map[x][y] - 1][now_dir - 1][index] - 1]
                    if nx >= 0 and nx < N and ny >= 0 and ny < N:
                        if smell[nx][ny][0] == Map[x][y]:
                            directions[Map[x][y] - 1] = shark_priority[Map[x][y] - 1][now_dir - 1][index]
                            temp[nx][ny] = Map[x][y]
                            break

    Map = temp
    time += 1

    check = True
    for i in range(N):
        for j in range(N):
            if Map[i][j] > 1:
                check = False

    if check:
        print(time)
        break

    if time >= 1000:
        print(-1)
        break
'''
# 순서 (큰틀)
1. 모든 상어가 자신의 위치에 냄새를 뿌린다.
2. 그 후에 1초마다 모든 상어가 이동하고 자신의 냄새를 그 칸에 뿌린다.
(냄새는 상어가 K번 이동하면 사라진다.)

# 제약 (상어 이동방향)
우선순위가 있음!
1. 아무냄새가 없는 칸 ( 순서는 정해진 우선순위에 따라서 변동 ) 
2. 모든 칸에 냄새가 차있으면, 자신의 냄새가 있는 칸을 선택
(만약 가능한 칸이 여러개이면, 그땐 정해진 우선순위에 따라 변동된다)

'''

 

 

참고 출처 : 이것이 코딩테스트다 with python