BOJ_4195 친구 네트워크

• TOC {:toc}

이 글은 백준 온라인 저지의 4195번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.02 (Python)

틀린 풀이입니다. 정답은 참고 답안을 참고해주세요.

# 메모리 초과
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    F = {}
    for i in range(int(input())):
        A, B = input().split()
        if A not in F:
            F[A] = set([B])
        else:
            F[A].add(B)
        if B not in F:
            F[B] = set([A])
        else:
            F[B].add(A)

        F[A] = F[A].union(F[B])
        F[B] = F[B].union(F[A])

        print(len(F[A]))

# 시간 초과
import sys
input = sys.stdin.readline

def get_index(key, F):
    i = 0
    while i < len(F):
        if key in F[i]:
            return i
        i += 1
    F.append(set([key]))
    return i

for _ in range(int(input())):
    F = []
    for i in range(int(input())):
        A, B = input().split()

        a = get_index(A, F)
        b = get_index(B, F)

        if a != b:
            F[min(a, b)] = F[a] | F[b]
            del F[max(a, b)]

        print(len(F[min(a, b)]))

디버그

• 입력받은 이름을 key로, 소속된 친구 네트워크 리스트를 value로 하는 딕셔너리를 만들어서 입력될 때마다 상호 추가한 다음 두 리스트를 합쳐서 친구 네트워크를 업데이트한 뒤 리스트의 길이를 출력하려고 했다.
  • 메모리 초과가 났다.
  • 친구 네트워크를 이름마다 부여해서 일일히 늘리는 게 비효율적일 거라 생각했는데 아예 조건을 넘겼다.
• 다음으로 친구 네트워크를 ‘하나’의 리스트로 만들고 입력받은 이름이 속해있는 리스트를 합쳐서 업데이트한 뒤 리스트의 길이를 출력해보려고 했다.
  • 시간 초과가 났다.
  • 확실히 친구 네트워크를 직접 합쳐나가면 입력이 많을 경우 감당이 안 되는 것 같다.
• 친구 네트워크는 리더 한 사람에서만 접근할 수 있고, 연결된 친구들은 리더를 가리키는 방식으로 구현해보려고 했는데 친구 네트워크를 직접 리스트로 나타내지 않고는 리더가 자신을 가리키는 친구에게 접근할 방법을 생각해내지 못해서 결국 풀이를 참고했다.
• 추가로 이름에 따라 값에 쉽게 접근하려면 딕셔너리를 이용하는 게 좋고, 리더를 가리키려면 클래스를 사용해 이름이 리더 프로퍼티를 가져야 하는데 이 둘을 효율적으로 이용해, 사람과 그 사람의 리더, 그 사람이 소속된 친구 네트워크를 나타내지를 못했다.

피드백

• 속도는 다음 두 포인트를 놓쳐서 해결하지 못한 것 같다.
  • 친구 네트워크를 직접 리스트로 관리하지 않고 친구의 ‘수’만 관리한다.
  • 친구 네트워크를 합칠 때마다 모든 사람의 리더와 친구 수를 업데이트하는 것이 아니라, 매번 속한 친구 네트워크의 리더를 찾은 뒤 ‘리더의 친구 수만’ 관리한다.
    • 출력할 때도 리더를 찾은 뒤 ‘리더의 친구 수’를 출력하면 문제가 되지 않는다.
• 자료구조와 관련해서는 다음 사항이 포인트인 것 같다.
  • 이름을 키로 사용하는 딕셔너리이다.
  • 자신의 리더와 친구의 수만 관리하면 되고, 동일한 키로 접근한다.
  • 참고 답안에서는 자신의 리더와 친구의 수 딕셔너리를 ‘각각’ 만들어서 관리했다.

2022.03.19 (JS)

방법 읽고 다시풀이

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const [T, ...E] = input;

function find(L, n) {
    if (n !== L[n]) {
        L[n] = get_leader(L, L[n]);
    }
    return L[n];
}

function union(L, C, a, b) {
    const la = find(L, a);
    const lb = find(L, b);

    if (la !== lb) {
        L[lb] = la;
        C[la] += C[lb];
    }

    return C[la];
}

function main(pairs) {
    const L = {}; // leaders(parents)
    const C = {}; // counts of networks
    const res = [];

    pairs.forEach((pair) => {
        const [a, b] = pair.split(" ");

        function create(n) {
            L[n] = n;
            C[n] = 1;
        }

        if (!L[a]) create(a);
        if (!L[b]) create(b);

        res.push(union(L, C, a, b));
    });

    console.log(res.join("\n"));
}

let j = 0;

for (let i = 0; i < T; i += 1) {
    const F = parseInt(E[j]);
    main(E.slice(j + 1, j + F + 1));
    j += F + 1;
}

디버그

• 시간 초과의 핵심도 아니었고, 당연하긴 하지만, Set에 add 하는 것보다 Array에 push하는 게 훨씬 빠르다고 한다.
  • Javascript Set vs. Array performance by stackoverflow
  • 자바스크립트 - Array VS Set
• 속도에 가장 큰 영향을 미치는 것은 Find 할 때 L을 훑어 올라가면서 각 값을 최상단 L 값으로 바꿔주는 것이었다.
  • 실행 시간 10000ms 대에서 600ms 대로 감소
  • 그 외에 res의 범위나 if 조건 등은 속도에 크게 영향을 미치지 않았다.

피드백

• 저번이랑 똑같이 자료구조라서 Find & Union으로 해결 할 생각 못하고 결국 시간/메모리 초과를 해결하지 못했다 ㅠ
• console.log()로 매 줄 출력하지 말고 res에 push 한 다음 \n으로 join 해서 출력하기

참고 답안

import sys
input = sys.stdin.readline

def get_leader(A):
    if A == leader[A]:
        return A
    else:
        # 입력된 사람의 '리더의 리더'를 l로 받아온다.
        l = get_leader(leader[A])
        # 입력된 사람의 리더를 받아온 l로 바꾼다.
        leader[A] = l
        # 받아온 l을 반환한다.
        return l

def connect(A, B):
    # A와 B의 최종 리더를 받아 다시 A, B에 입력한다.
    A, B = get_leader(A), get_leader(B)

    # A와 B가 다르면
    if A != B:
        # B의 리더를 A로 지정하고
        leader[B] = A
        # A의 친구 수에 B의 친구 수를 더한다.
        f_num[A] += f_num[B]

for _ in range(int(input())):
    leader = {}
    f_num = {}

    for _ in range(int(input())):
        A, B = input().split()

        if A not in leader:
            leader[A] = A
            f_num[A] = 1
        if B not in leader:
            leader[B] = B
            f_num[B] = 1
        
        # A와 B를 연결한다.
        connect(A, B)
        # A의 최종 리더의 친구 수를 출력한다.
        print(f_num[get_leader(A)])

아이디어 & 풀이

get_leader는 입력된 사람부터 그 사람이 속한 친구 네트워크의 최종 리더(i.e., L)까지 도달하는데 거치는 모든 사람의 리더를 L로 바꾸고 L을 반환한다.

• 재귀 용법과 최종 리더는 자기 자신을 리더 값으로 갖는다는 것을 이용한다.

• 예를 들어 다음과 같은 리더 관계를 갖는다고 하면 (최종 리더: D) 그다음 표와 같이 실행된다.

  입력된 사람	A	B	C	D
  현재 리더	B	C	D	D

  실행 순서	statement	실행 순서	statement
  1	A = get_leader(A)	9	A = D
  2	l = get_leader(B)	8	l = D, leader[A] = D return D
  3	l = get_leader(C)	7	l = D, leader[B] = D return D
  4	l = get_leader(D)	6	l = D, leader[C] = D return D
  5	return D

connect는 입력받은 두 사람의 최종 리더 중 한 사람을 정해 새로운 최종 리더로 만들고 그 사람의 친구 수를 업데이트한다.

• 예를 들어 A와 B의 최종리더를 A'과 B'이라고 할 때 B'의 리더를 자기 자신에서 A'으로 바꾸고 A'의 총 친구 수를 업데이트한다.
  • 반대로 해도 상관없다.
• 이 과정에서 B' 친구 네트워크 사람들의 리더가 A'으로 바뀌는 것은 아니지만 어차피 출력할 때 get_leader를 호출하면 B'에 도달한 이후 다시 A'로 가기 때문에 상관없다.