[SWEA] 2382. 미생물 격리(Python) / Simulation

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

SW Expert Academy

# 47분 소요

사실 이 문제도 5번? 정도 푼 문제라서 풀 때마다 Pass까지의 시간이 단축되는 것 같다 ㅋㅋㅋ

특별히 사용한 알고리즘은 없고, 이차원 배열과 딕셔너리 자료구조를 이용했다.

겉으로는 Simulation이지만, 일일이 맵을 만들 필요는 없어 보였고, 이차원 배열을 만들어 M시간만큼 이차원 배열에 들어있는 미생물의 정보(위치, 미생물갯수, 방향)를 변화시키는 방식으로 접근했다.

그냥 생각나는대로 직관적으로 풀었다.

• M시간만큼 for문을 돌리면서
  • 미생물 갯수 0이면 보지 않음. 
  • 해당 미생물의 위치 이동, 이때 약품이 칠해진 곳이라면 방향 반대로 전환하고, 갯수 절반으로 줄여준다.
  • 이동 후 정보를 (새 위치) : [갯수, 크기] 형태로 info 딕셔너리에 넣어준다.
• 각 미생물의 이동이 끝나고 나면 충돌 여부를 파악한다.
  • 해당 위치에 충돌한 것이 아니라면 그대로 미생물 갯수와 방향을 갱신
  • 충돌했을 때 따로 처리해준다.
    • 미생물 갯수가 가장 많은 것의 인덱스에 충돌한 위치에 있는 미생물 갯수의 합으로 갱신, 방향은 그대로
    • 미생물 갯수가 적어 흡수되는 인덱스의 미생물 갯수는 0으로 바꿔준다.
• 최종적으로 남은 미생물 갯수의 합을 total 변수에 담아 출력

 

파이썬 코드는 다음과 같다.

---

import sys
sys.stdin = open("2382_input.txt")

# 상하좌우
dr = (0, -1, 1, 0, 0)
dc = (0, 0, 0, -1, 1)
rev = (0, 2, 1, 4, 3)

# main
T = int(input())
for tc in range(T):
    N, M, K = map(int, input().split())
    microbe = [list(map(int, input().split())) for _ in range(K)]

    # M시간 움직임
    for _ in range(M):
        info = dict()
        for idx in range(K):
            r, c, n, d = microbe[idx]
            if not n:   # 소멸된 미생물은 검사 X
                continue
            nr = r + dr[d]
            nc = c + dc[d]
            microbe[idx][0], microbe[idx][1] = nr, nc	# 새 위치 갱신
            if not (1 <= nr < N-1 and 1 <= nc < N-1):
                n //= 2         # 미생물 수 절반
                d = rev[d]      # 방향 전환

            # 미생물 수, 방향 저장
            if (nr, nc) not in info.keys():
                info[(nr, nc)] = [(idx, n, d)]
            else:
                info[(nr, nc)].append((idx, n, d))

        # microbe 갱신 - 충돌하지 않았을 때, 충돌했을 때 처리
        for values in info.values():
            if len(values) == 1:    # 충돌 X
                i, n, d = values[0]
                microbe[i][2] = n
                microbe[i][3] = d
            if len(values) > 1:     # 충돌 O
                total = 0
                maxIdx, maxCnt, maxDir = -1, -1, -1
                for i, n, d in values:
                    total += n
                    if maxCnt < n:
                        maxIdx = i
                        maxCnt = n
                        maxDir = d
                microbe[maxIdx][2] = total
                for i, n, d in values:
                    if i != maxIdx:
                        microbe[i][2] = 0   # 미생물 흡수
    remains = 0
    for r, c, n, d in microbe:
        remains += n
    print("#{} {}".format(tc+1, remains))

• 시간 : 795ms / 메모리 : 68,728kb

---

 

위 코드는 사실 좀 마음에 들지 않는 코드다. 

저번에 짠 코드는 딕셔너리에 새 위치, 갯수, 방향 정보를 담으면서 갱신시켜 for문 한 방에 끝냈었다. 시간도 공간도 훨씬 절약할 수 있고 for문도 한 번이라 훨씬 깔끔한 코드라 더 마음에 든다!

---

dr = (0, -1, 1, 0, 0)
dc = (0, 0, 0, -1, 1)
rev = (0, 2, 1, 4, 3)

T = int(input())
for tc in range(T):
    N, M, K = map(int, input().split())
    A = []
    for _ in range(K):
        A.append(list(map(int, input().split())))

    for _ in range(M):
        info = dict()
        for row in range(K):
            r, c, k, d = A[row]
            if not k:
                continue
            nr = r + dr[d]
            nc = c + dc[d]
            A[row][0], A[row][1] = nr, nc
            if not (1 <= nr < N-1 and 1 <= nc < N-1):
                A[row][2] //= 2
                A[row][3] = rev[d]
            if (nr, nc) not in info.keys():
                info[(nr, nc)] = [row, k]
            else:
                num, size = info[(nr, nc)]
                if A[row][2] > size:
                    info[(nr, nc)] = [row, A[row][2]]
                    A[row][2] += A[num][2]
                    A[num][2] = 0
                else:
                    A[num][2] += A[row][2]
                    A[row][2] = 0
    microbe = 0
    for m in A:
        microbe += m[2]
    print("#{} {}".format(tc+1, microbe))

• 시간 : 630ms / 메모리 : 68,728 kb

---

• 고찰 : for 문 한 번에 쓸 수 있는 문제라면 그렇게 풀자. 쉬운 길을 돌아가지 말자. 고려할 것이 생각보다 많지 않은 문제라서 쉽게 풀렸던 문제다.