[BOJ] 19237번 - 어른상어 (삼성 SW 기출)

최근에 다시 삼성 SW 역량 테스트 관련 문제들을 풀어 보았다. 포스팅 한 것 외에 톱니바퀴 문제 등의 문제들을 풀어 보았다.

그 중에서도 어른 상어... 진짜 상어 관련 문제들은 항상 구현할 때마다 머리가 터질것 같았다. 아직 실력이 부족한 것 같다.

별 다른 알고리즘은 필요없고, 말 그대로 구현, 시뮬레이션 문제들이다.

 

보통 삼성의 문제들은 구현문제들이 많이 출제되었던 것같다. 구현과 완전탐색이 주된 문제로 나왔다.

카카오의 경우도 구현문제가 적지않게 출제되곤 한다. 하지만 이런식의 구현문제와는 느낌이 살짝 다르다.

예를들어 자료구조를 활용하여 N^2을 NlogN 이나 N 방법으로 계산이 가능하게 하는 이런 방법들을 카카오에서는 많이 봤던 것 같다.

 

이번 문제도 역시 구현 문제이다. 앞으로 어떤 것을 저장해줄때 통일해주는 습관이 중요한 것 같다.

예를들어 방향은 1 2 3 4 이고 상어의 번호도 1 2 3 4 라면 0부터 채워 넣게끔 입력을 그렇게 받던지 아니면, 1부터 채워 넣게끔 입력을 받던지 하나로 해야겠다. 중간중간에 고친다고 애를 좀 먹었다..

 

www.acmicpc.net/problem/19237

19237번: 어른 상어

문제를 봤을 때 되게 조건이 까다롭고 저장을 효율적으로 해야 될 것같은 그런 느낌이 들었다..

 

입력받을 때 활용할 저장공간

1. 격자를 입력받으면서 shark[] 배열에 (행, 열, 번호, 방향)을 넣는다.

 

2. 상어들의 우선순위를 shark_priority[] 배열에 넣어 저장한다.

 

시뮬레이션을 위한 저장공간

1. smell[] 배열을 두어 상어가 지나간 곳의 냄새를 저장하는 공간을 둔다.

( 이미 냄새가 있는곳에 상어가 도착하여 냄새를 뿌리면 냄새는 덮어씌워 진다.!!! )

 

2. 상어들이 움직일 때 dictionary 자료구조를 통해 각 좌표에 상어들이 얼마나 있는지 저장한다.

ex) dic[(1,2)] = [(shark_number, direction), (shark_number, direction)]  // 1,2 좌표에 상어가 두 마리가 들어있다.

 

구현할 때 주의할 점!!

1. 상어가 이동을 하게 되면 이동하는 방향으로 shark[] 배열에 저장을 해주어야한다.

 

2. 냄새는 정해진 k 값으로 시뮬레이션이 끝날 때까지 k 값으로 유지된다.

 

3. 냄새가 0 일때 잘 초기화 해주기

 

시뮬레이션 순서

1. 상어는 각자의 위치에서 냄새를 뿌린다.

 

2. 상어가 움직인다.(상어의 번호와 방향을 토대로 우선순위를 잘 파악한 뒤 탐색을 하고 빈 자리 탐색과 자기 자신의 냄새로 돌아가는 예외 처리를 잘 해줘야 한다.)

 

3. 냄새들의 수명을 1만큼 줄인다.

 

from sys import stdin

std = stdin.readline

N, M, k = map(int, std().split())

shark = [[] for i in range(M)]  # row, column, direction
smell = [[[]for i in range(N)] for i in range(N)]

for i in range(N):
    s = list(map(int, std().split()))
    for j in range(N):
        if s[j] != 0:
            num = s[j]
            shark[num-1] = [i, j, s[j]-1, 0]

direct = list(map(lambda x: int(x) - 1, std().split()))

for i, d in enumerate(direct):
    shark[i][3] = d

shark_priority = [[] for i in range(M)]

nr, nc = [-1, 1, 0, 0], [0, 0, -1, 1]  # 위 아래 왼 오

for i in range(M*4):
    shark_priority[i//4].append(list(map(lambda x: int(x)-1, std().split())))


def remain_smell(time):
    for i in range(len(shark)):
        r, c, num, d = shark[i]
        smell[r][c] = [num, time]


def reduce_smell():
    for i in range(N):
        for j in range(N):
            if len(smell[i][j]) > 0:
                smell[i][j][1] -= 1
                if smell[i][j][1] == 0:
                    smell[i][j] = []


def move_shark():
    global shark
    dic = {}  # 상어 모음
    for i in range(len(shark)):
        # 빈 자리 있는지 확인
        r, c, num, d = shark[i]
        priority = shark_priority[num][d]  # i번 상어가 d방향을 볼 때 우선순위
        flag = 0
        me_r, me_c = 0, 0
        for p in priority:
            dr, dc = r+nr[p], c+nc[p]
            if 0 <= dr < N and 0 <= dc < N:
                if len(smell[dr][dc]) == 0:  # 냄새가 빈자리로 이동
                    if (dr, dc) not in dic:
                        dic[(dr, dc)] = [(num, p)]
                    else:
                        dic[(dr, dc)].append((num, p))
                    flag = 1
                    break
                elif flag == 0 and smell[dr][dc][0] == num:  # 우선순위가 제일 높은 나의 냄새를 저장
                    flag = 2
                    me_r, me_c, me_num, me_d = dr, dc, num, p

        if flag == 2:
            if (me_r, me_c) not in dic:
                dic[(me_r, me_c)] = [(me_num, me_d)]
            else:
                dic[(me_r, me_c)].append((me_num, me_d))

    shark = []

    for key in dic:
        row, column = key
        if len(key) > 1:
            dic[key].sort()
            dic[key] = [dic[key][0]]
        shark.append([row, column, dic[key][0][0], dic[key][0][1]])


t = 0
while True:
    t += 1
    remain_smell(k)
    move_shark()
    reduce_smell()

    if t > 1000 or len(shark) == 1:
        break

print(t if t != 1001 else -1)