Easy is Perfect

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

  • melonicedlatte
  • Mar 27, 2021


1. 문제

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

2. 풀이

삼성 SW 역량테스트 문제입니다. 풀이 순서는 아래와 같습니다.

  1. 이 문제는 상어가 move 하면서 주변 냄새를 남긴 곳들의 값이 1씩 감소합니다. 이러한 과정을 수행하기 위하여 함수로 나눴습니다.
    • move(상어들을 이동시킴) : 가능한 갈 수 있는 곳 모두 체크 -> 주변에 빈 곳과 자신의 냄새가 있는 곳을 찾음 -> 주변에 빈 곳이 있으면 우선순위 높은거 선택. 없으면 냄새가 있는 곳에서 우선순위 높은거 선택.
    • minus_smell(냄새 값들을 1씩 감소시킴)
    • drop_smell(이동시킨 상어들의 위치에 냄새를 남김)
  2. 자료구조는 대부분 list를 사용했습니다. 상어들의 위치와 남은 시간은 map을 따로 생성하여 사용했습니다.
    • shark_maps : 상어들의 위치
    • smell_maps : 냄새를 남긴 상어와 남은 시간

삼성문제들의 특성으로 간단한 구조이지만 조건들이 많이 복잡합니다. index 관리를 매우 잘 해주어야 합니다(예를 들어, index는 0~N-1 이고 상어는 1~N을 사용하는 경우). 저도 index 관리를 잘 못해서 오답에 빠지는 경우가 많았습니다.

# 위, 아래, 왼쪽, 오른쪽
UP, DOWN, LEFT, RIGHT = [1, 2, 3, 4]
N, M, k = map(int, input().split())
shark_maps = [list(map(int, input().split())) for _ in range(N)]
shark_way = list(map(int, input().split()))
shark_priority = [[list(map(int, input().split())) for _ in range(4)] for __ in range(M)]
# 앞에는 상어, 뒤에는 남은 시간
smell_maps = [[[0, 0] for __ in range(N)] for _ in range(N)]
dr = [-1,1,0,0]
dc = [0,0,-1,1]

# 향기 남기기
def drop_smell():
    for r in range(N):
        for c in range(N):
            if shark_maps[r][c] == 0:
                continue
            smell_maps[r][c] = [shark_maps[r][c], k]

# 향기 값 -1
def minus_smell():
    for r in range(N):
        for c in range(N):
            if smell_maps[r][c][0] == 0:
                continue
            smell_maps[r][c] = [(smell_maps[r][c][0] if smell_maps[r][c][1]-1 != 0 else 0), smell_maps[r][c][1]-1]

# 이동하기
def move():
    global shark_maps
    sub_maps = [[[] for __ in range(N)] for _ in range(N)]
    for r in range(N):
        for c in range(N):
            shark_num = shark_maps[r][c]
            if shark_num == 0:
                continue
            # 다음 가능한 갈 수 있는 곳 모두 체크
            empty = []
            my_smell = []
            for w_idx in range(1, 4+1):
                next_row = r + dr[w_idx-1]
                next_col = c + dc[w_idx-1]
                if next_row < 0 or next_row >= N or next_col < 0 or next_col >= N:
                    continue

                ## 주변에 빈 곳 찾기
                if smell_maps[next_row][next_col] == [0,0]:
                    empty.append(w_idx)
                ## 빈 곳이 없으면 자신의 냄새가 있는 곳
                elif smell_maps[next_row][next_col][0] == shark_num:
                    my_smell.append(w_idx)
            next_can = my_smell if len(empty) == 0 else empty

            # 다음 갈 곳 확인
            next = False
            for w_idx in shark_priority[shark_num-1][shark_way[shark_num-1]-1]:
                if next != False:
                    break
                for n in next_can:
                    if w_idx == n:
                        next = w_idx
                        break

            if next == False:
                continue
            next_row = r + dr[next-1]
            next_col = c + dc[next-1]
            sub_maps[next_row][next_col].append(shark_num)
            shark_way[shark_num-1] = next

    # 이동한 얘들 중 최소만 남기고 다음 맵으로 갱신
    shark_maps = [[(min(sub_maps[r][c]) if len(sub_maps[r][c]) else 0) for c in range(N)] for r in range(N)]


# 이동하기 & 이전 요소들 다 1씩 감소
drop_smell()
t = 1
while t <= 1000:
    move()
    minus_smell()
    drop_smell()

    # 상어 수 세기
    shark_num = 0
    for r in range(N):
        for c in range(N):
            shark_num += shark_maps[r][c]
    if shark_num == 1:
        print(t)
        break
    t+=1

# 제일 번호 낮은 얘만 남기고 죽이기
if t > 1000:
    print(-1)



Search