JinWoo Kim

백문이 불여일견, 백견이 불여일행.

3 minute read

1. 바이러스

  • 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.

  • 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

  • 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.
  • 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.
  • 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

그림 1

  • 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

  • 첫째 줄에는 컴퓨터의 수가 주어진다.
    • 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
  • 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
  • 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

  • 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

풀이

import sys


def dfs(x, visited):
    if x not in visited:
        visited.append(x)
        for k in graph[x]:
            if k != N + 1:
                dfs(k, visited)

    return visited


N = int(sys.stdin.readline())
graph = [[N + 1] * N for _ in range(0, N)]

for _ in range(int(sys.stdin.readline())):
    a, b = [int(x) for x in sys.stdin.readline().strip('\n').split()]
    graph[a - 1][b - 1] = min(graph[a - 1][b - 1], b - 1)
    graph[b - 1][a - 1] = min(graph[b - 1][a - 1], a - 1)

print(len(dfs(0, []))-1)

채점 결과

  • 정답

리뷰

  • 말이 많지만 결국 그래프를 그리고, 1번 컴퓨터에 해당하는 정점과 연결된 모든 정점의 개수를 반환하는 문제이다.

  • dfs 사용해서 1번 정점에 연결된 모든 정점을 return하고, 그 개수에서 1 빼주어(자기 자신은 포함 안하는것을 예제로 확인 가능했다.) 답을 도출했다.

2. 집합

  • 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오.

    • add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
    • remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
    • check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
    • toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
    • all: S를 {1, 2, …, 20} 으로 바꾼다.
    • empty: S를 공집합으로 바꾼다.

입력

  • 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다.

  • 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다.

출력

  • check 연산이 주어질때마다, 결과를 출력한다.

풀이

import sys

order_dic = {
    "add": lambda S, x: S | {x} if not S & {x} else S,
    "remove": lambda S, x: S - {x} if S & {x} else S,
    "check": lambda S, x: S if print(1 if S & {x} else 0) else S,
    "toggle": lambda S, x: S | {x} if not S & {x} else S-{x},
    "all": lambda S: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
    "empty": lambda S: set()
}

S = set()
for _ in range(int(sys.stdin.readline())):
    order = sys.stdin.readline().strip('\n').split()
    if len(order) == 2:
        S = order_dic[order[0]](S, int(order[1]))
    else:
        S = order_dic[order[0]](S)

채점 결과

  • 정답

리뷰

  • 결과만 놓고 보면, 고수인척 한번 해보려고 딕셔너리 + lambda + set함수를 통한 집합 연산을 도입했다가 괜히 시간만 겁나게 잡아먹은 바보같은 풀이였다.

  • 이번 문제에서 이런 방식을 쓰면 안되었던 이유를 위주로 설명하자면, 다음과 같다.

    • 딕셔너리 + 람다식 사용
      • = 기호의 사용 불가로 인해 간단한 등호나 명령문으로 끝날 문제가 화려하게 꼬여버렸다.
    • Set함수를 통한 집합연산
      • 위의 딕셔너리/람다식 문제의 연장선인데, 위 문제로 인해 리스트에 뭘 넣거나 빼는 연산이 힘들어져 Set을 사용하게 되었고, 불필요한 교집합 연산등을 사용하게 되면서 시간 복잡도가 미친듯이 늘어났다.

  • 이번 문제의 교훈

    • 나대지 말고, 기본기에 집중하자.

더 나은 풀이

import sys
l = []
for _ in range(int(sys.stdin.readline())):
    comm = sys.stdin.readline().split()
    if comm[0] == "add":
        if comm[1] in l:
            continue
        else:
            l.append(comm[1])
    if comm[0] == "remove":
        if comm[1] in l:
            l.remove(comm[1])
    if comm[0] == "check":
        sys.stdout.write('1\n' if comm[1] in l else '0\n')
    if comm[0] == "toggle":
        if comm[1] in l:
            l.remove(comm[1])
        else:
            l.append(comm[1])
    if comm[0] == "all":
        # for speed reason, not using for loop list
        l = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20']
    if comm[0] == "empty":
        l = []

더 나은 풀이 리뷰

  • 기본에 충실하되, 군데군데에서 최적화를 위해 노력한 흔적들이 보였다.

    • int로 변환하는 함수조차 사용하지 않기위한 문자열형식에서의 처리

    • 시간 이슈 해결을 위해 all함수를 루프를 사용하지 않고 직접 정의한 것.

    • sys.stdout.write()함수를 사용하여 print문에 비해 시간을 절약함.

You May Also Enjoy