[모의 SW 역량테스트] 미생물 격리

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl 

SW Expert Academy

 

#1. 설계 및 풀이

 

- 문제 : M시간 후 남아있는 미생물 수의 총합?

- 입력 : N*N [5, 10], 군집의 수 k[5, 100], 격리시간 m [1, 100], 군집 내 미생물 수 [1, 10000],
방향 상1하2좌3우4, 세로 가로 미생물 수 이동방향 순 입력 주어짐

- 출력 : 문제와 동일

- 조건 :
1) 1시간마다 해당 방향으로 이동
2) 군집이 양끝에 도달 -> 미생물 수//2, 이동방향 반대
3) 여러 군집이 한 셀에 모이면 미생물수 = 모두의 합, 이동방향 = 가장 수가 많은 군집의 이동방향

--> N이 100이므로 BFS/DFS + 시뮬이 가능하겠다.

 

1. 주어진대로 미생물 수와 방향을 저장

2. m번동안 반복

2-1) 방향으로 이동 -> 빈 temp에 저장

2-2) temp의 배열이 비어있지 않으면 temp에 저장된 값에 따라 board를 변경

 

2-2-1) r == 0 or r ==n or c == 0 or c == n이면 미생물 절반, 방향은 반대

(** 방향 반대를 여기서 습관처럼 (dir+1)%4로 설계한 바람에

디버깅의 늪에 빠져버렸다 ^^... 제발 아는 것도 의심 또 의심 !!)

 

2-2-2) 아니고 temp 배열 길이가 1보다 크면

각각의 값을 저장해두고 미생물의 수는 모두의 합, 이동방향은 가장 많은 수를 가진 군집의 이동방향

 

2-2-3) temp 배열 길이 1이면 그대로 board에 저장

 

3) 총합 구하기

 

T = int(input())
dx = [-1, 1, 0, 0] # 상하좌우
dy = [0, 0, -1, 1]
for test_case in range(1, T + 1):
    n, m, k = map(int, input().split())
    board = [[0] * n for _ in range(n)]
    for _ in range(k) :
        x, y, num, dir = map(int, input().split())
        board[x][y] = [num, dir-1]

    for _ in range(m) : # m시간동안 반복
        temp = [[[] for _ in range(n)] for _ in range(n)]
        for i in range(n) :
            for j in range(n) :
                if board[i][j] != 0 :
                    num, dir = board[i][j]
                    nx, ny = i + dx[dir], j + dy[dir]
                    temp[nx][ny].append([num, dir])
                    board[i][j] = 0

        for i in range(n) :
            for j in range(n) :
                if not temp[i][j] :
                    continue
                if i == 0 or i == n-1 or j == 0 or j == n-1 :
                    num, dir = temp[i][j][0]
                    if dir in [0, 2] :
                        dir = dir+1
                    elif dir in [1, 3] :
                        dir = (dir+3) % 4
                    board[i][j] = [num//2, dir]
                elif len(temp[i][j]) > 1 :
                    total, max_idx = 0, 0
                    arr = temp[i][j]
                    for idx in range(len(arr)) :
                        total += arr[idx][0]
                        if arr[max_idx][0] < arr[idx][0] :
                            max_idx = idx
                    board[i][j] = [total, arr[max_idx][1]]
                elif len(temp[i][j]) == 1 :
                    board[i][j] = temp[i][j][0]

    answer = 0
    for i in range(n) :
        for j in range(n) :
            if board[i][j] != 0 :
                answer += board[i][j][0]

    print("#" + str(test_case), answer)

 

#2. 배운 점

 

- 문제 풀이 접근까지는 성공했는데

방향이 1, 2, 3, 4로 주어져서 dx, dy의 길이를 5로 설정해서 틀린줄 알고 봤더니

방향 반대이면 무조건 (dir+1) % 4가 아니라 방향에 따라 다르게 정의해줬어야 했다..

--> 익숙한 것이라도 한번 더 확인하는 습관을 들이자 !