[python] SWEA - 7465. 창용 마을 무리의 개수 / 10200. 구독자 전쟁

1. 창용 마을 무리의 개수

문제 해결

D4 | DFS, BFS, 그래프

1. 주어진 정보로 인접리스트를 만든다.

2. 보통의 그래프 탐색이라면 시작점하나로 BFS나 DFS 탐색을 하고 끝나지만 여기서는 모든 노드를 탐색해야 하므로

3. BFS탐색을 하는 while문을 for문으로 감싸서 모든 노드를 탐색한다.

4. for문을 통해 큐에 들어가는 노드는 한 무리의 시작점이므로 카운트를 세어준다.

 

🌦 처음 실패는 while 문 안에 for 문을 넣어 시간초과가 났다는 것이다. 여기서 for 문을 바깥으로 꺼내주고 시간초과는 해결, 두번째 실패는 for문을 N까지 돌려서 났다. N+1로 고쳐서 통과했다.

 

소스 코드

from _collections import deque

for tc in range(1, 1 + int(input())):
    N, M = map(int, input().split())
    # 인접리스트 생성
    adj = {x + 1: [] for x in range(N)}
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    # 방문확인, 큐, 무리의 갯수
    visited = [0] * (N + 1)
    visited[0] = 1
    q = deque()
    cnt = 0

    # 전체 무리를 찾아야 하므로 for문으로 1명씩 큐에 집어넣는다.
    for i in range(1, N+1):
        # 아직 방문하지 않았을 경우에만
        if visited[i] == 0:
            cnt += 1
            q.append(i)
            visited[i] == 1

        # BFS 탐색색
        while q:
            c = q.popleft()
            for neighbor in adj[c]:
                if visited[neighbor] == 0:
                    q.append(neighbor)
                    visited[neighbor] = 1

    print('#{} {}'.format(tc, cnt))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE

SW Expert Academy

창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다. 두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 이러한 사람들을 모두 다 묶어서 하나의 무리라고 한다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는 두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다. 이후 M개의 줄에 걸쳐서 서로를 알고 있는 두 사람의 번호가 주어진다. 같은 관계는 반복해서 주어지지 않는다. [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 무리의 개수를 출력한다.

2. 구독자 전쟁

문제 해결

D3 | 수학?

1. 두 채널을 모두 구독하는 최소 구독자 수는 P채널 구독자와 T채널 구독자를 더하고 N 을 빼준다.

2. N이 음수라면 최소 구독자는 0

3. 두 채널을 모두 구독하는 최대 구독자 수는 P채널 구독자와 T채널 구독자 중 더 작은 수와 같다.

 

🌤 단순한 수학 문제인거 같다. 쉽게 풀기 위해 min, max를 사용했다.

 

소스 코드

for tc in range(1, 1 + int(input())):
    n, a, b = map(int, input().split())

    max_answer = min(a, b)
    
    min_answer = a + b - n
    if min_answer < 0:
        min_answer = 0

    print('#{} {} {}'.format(tc, max_answer, min_answer))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWngfZVa9XwDFAQU&categoryId=AWngfZVa9XwDFAQU&categoryType=CODE

SW Expert Academy

최근 어떤 동영상 플랫폼에서 P채널과 T채널이 구독자 수 1위를 놓고 치열한 경쟁을 벌이고 있다. 영은이는 자신의 주위 사람들은 어떤 채널을 구독하고 있을지 궁금해하여, N명의 사람들에게 아래 두 질문을 하였다.     -  P채널을 구독하고 있나요?     -  T채널을 구독하고 있나요?   그 결과, A명이 1번 질문에 ‘네’라고 답했고, B명이 2번 질문에 ‘네’라고 답했다. 이때, P채널과 T채널 모두 구독하고 있는 사람들이 최소 몇 명, 최대 몇 명인지 구하는 프로그램을 작성하라.   [입력]   첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 세 개의 정수 N (1 ≤ N ≤ 100), A, B (0 ≤ A, B ≤ N)이 공백 하나를 사이로 두고 순서대로 주어진다.   [출력]   각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, P채널과 T채널 모두 구독하고 있는 사람의 수의 최댓값과 최솟값을 공백 하나를 사이로 두고 차례대로 출력한다.