Q48. 어른 상어

삼전 기출 3문제 있는데 어려운거부터 역순으로 풀자 그래야 마음이 편할거같다

19237번: 어른 상어 (acmicpc.net)

19237번: 어른 상어

 

삼전 코테 이런식으로 나오는구나

보통 2문제 정도 나오는걸로 아는데 1문제 맞추면 통과인 경우도 많다 들었다.

보니까 dfs/bfs, 시뮬레이션, 완전탐색 문제가 주로 나오고 발상은 어렵지 않은데 깔끔하게 구현하기 어려운 문제들이 대부분인거같다. 빡세빡세~

 

자 이런문제들은 보통 여러가지 함수로 나눠서 풀면 좀 쉽게 풀수있다. 잘 나눠서 풀어보자 침착하고 꼼꼼하게..

 

인풋 받는거부터 욕나온다 ㅋㅋㅋㅋㅋㅋㅋ

 

(다 푼 후)

와 진짜 장난하낰ㅋㅋㅋ

이 문제는 구현 피지컬이 정말 많이 필요하다

삼전은 이런문제를 좋아하는구나;;

 

#grid의 한 변의 크기, 상어의 수, k
N, M, K = map(int, input().split())

# N * N 그리드
grid = []
for _ in range(N):
    grid.append(list(map(int, input().split())))

# N * N 스멜
smell = [[[0, 0]] * N for _ in range(N)]

# 방향 d 위 아래 왼쪽 오른쪽
dx = [0, -1, 1, 0, 0]
dy = [0, 0, 0, -1, 1]

# 각 상어의 방향
directions = [-1] + list(map(int, input().split()))

# 각 상어의 우선순위 : shape (상어번호, 현재방향, 우선순위)
priority = [[-1] for _ in range(M + 1)]
for i in range(1, M + 1):
    for _ in range(4):
        priority[i].append(list(map(int, input().split())))

#냄새정보 업데이트
def update_smell():
    for i in range(N):
        for j in range(N):
            if smell[i][j][1] > 0:
                smell[i][j][1] -= 1
            if grid[i][j] != 0:
                smell[i][j] = [grid[i][j], K]


#다음 방향 얻기 (인자 : 상어번호, 현재방향, 우선순위 넘버)
def get_next_dir(num, curdir, index):
    return priority[ num ][ curdir ][ index ]

#가장 복잡한 함수 : 상어이동
def move():
    # tmp grid 초기화
    tmp_grid = [[0] * N for _ in range(N)]

    # 각 위치를 하나씩 확인
    for x in range(N):
        for y in range(N):
            #상어가 존재하면
            if grid[x][y] != 0:
                no_smell_found = False
                curdir = directions[grid[x][y]]

                #냄새가 존재하지 않는 곳 확인
                for i in range(4):
                    nxt_dir = get_next_dir(grid[x][y], curdir, i)
                    nx = x + dx[ nxt_dir ]
                    ny = y + dy[ nxt_dir ]
                    #냄새 없는 곳 있으면 상어 이동시키기
                    if nx >= 0 and nx < N and ny >= 0 and ny < N and smell[nx][ny][1] == 0:
                        if tmp_grid[nx][ny] == 0:
                            tmp_grid[nx][ny] = grid[x][y]
                        else:
                            tmp_grid[nx][ny] = min(tmp_grid[nx][ny], grid[x][y])
                        
                        no_smell_found = True
                        directions[grid[x][y]] = nxt_dir
                        break

                if no_smell_found:
                    continue

                #주변에 냄새가 남아 있으면 자신의 냄새가 있는 곳으로 이동
                for i in range(4):
                    nxt_dir = get_next_dir(grid[x][y], directions[grid[x][y]], i)
                    nx = x + dx[ nxt_dir ]
                    ny = y + dy[ nxt_dir ]

                    if nx >= 0 and nx < N and ny >= 0 and ny < N and smell[nx][ny][0] == grid[x][y]:
                        tmp_grid[nx][ny] = grid[x][y]
                        directions[grid[x][y]] = nxt_dir

                        break
                
    return tmp_grid

#main 로직
sec = 0
while True:
    # 냄새 카운트 1 감소
    update_smell()
    new_grid = move()
    grid = new_grid
    sec += 1

    # 1번 상어만 남아있으면 종료
    count = 0
    for i in range(N):
        for j in range(N):
            if grid[i][j] > 0:
                count += 1
                
    if count == 1:
        print(sec)
        break

    if sec >= 1000:
        print(-1)
        break