그래프 연습 (5) - 컴퓨터 세그먼트(문제 자체 변형)

* 해당 문제는 저작권에 문제가 될 수 있어, GPT를 활용하여 다른 문제로 치환하였습니다.

** 원본 문제는 기업 코테 기출문제, PCCP등 자격증 문제와 같이 평가가 이루어지는 기출문제가 아님을 알려드립니다.

 

체감 난이도: 실버 1

 

문제

컴퓨터 네트워크를 관리하는 관리자인 철수는 네트워크 상의 컴퓨터들이 어떻게 연결되어 있는지 파악하기 위해 네트워크를 그래프로 표현했습니다. 각 컴퓨터는 1부터 N까지의 고유 번호로 식별되며, 서로 연결된 컴퓨터들은 데이터를 직접 주고받을 수 있습니다. 이 연결은 양방향이며, 연결된 컴퓨터들은 같은 네트워크 세그먼트에 있다고 간주됩니다.

세그먼트의 식별자(ID)는 그 세그먼트 내에 속한 컴퓨터 중 가장 작은 번호로 정해집니다. 관리자는 네트워크 내에서 가장 많은 컴퓨터를 포함하고 있는 세그먼트의 ID를 식별해야 합니다. 세그먼트의 크기가 같다면, 더 작은 ID를 가진 세그먼트의 ID를 선택해야 합니다.

---

입력 설명: 첫 번째 줄에 네트워크 상의 컴퓨터 수 N과 연결 정보의 수 M이 주어집니다. 그 다음 M개의 줄에 걸쳐서 두 컴퓨터의 연결 정보가 주어집니다.

출력 설명: 가장 많은 컴퓨터를 포함하는 네트워크 세그먼트의 ID를 출력합니다. 만약 같은 크기의 세그먼트가 여러 개 있을 경우, 가장 작은 ID를 가진 세그먼트를 출력합니다.

 

예제 입력1

4 4
1 2
2 3
3 4
4 1

예제 출력1

1

예제 입력2

5 3
2 3
3 4
4 2

예제 출력2

2

 

입력값 설명

첫째 줄에 N과 M이 공백으로 구분되어 주어집니다. (2 ≤ N ≤ 100, 1 ≤ M ≤ 500)
이어서 M개의 줄에 거쳐 컴퓨터 연결 관계가 주어집니다. 각 줄에는 양의 정수 u, v가 공백으로 구분되어 주어집니다. 이는 u번 정점과 v번 정점을 잇는 간선이 존재함을 의미합니다. (1 ≤ u, v ≤ N, u ≠ v)

출력값 설명

첫째 줄에 가장 많은 컴퓨터가 포함된 세그먼트의 ID를 출력합니다. 단, 조건을 만족하는 세그먼트가 여러 개인 경우 그 중 가장 작은 ID를 출력합니다.

 

풀이

해당 문제는 컴퓨터의 개수가 주어질때, 모든 컴퓨터가 연결되어있다는 보장이 없습니다. 따라서 희소행렬이 될 수 있으므로 인접 리스트로 진행합니다. 

N, M = map(int, input().split())

# 인접 리스트를 사용
graph = [[] for _ in range(N+1)]
for i in range(M):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

인접 리스트, 인접 행렬에 관한 글은 아래 링크를 참고해주세요.

2023.11.08 - [Algorithm/Graph] - 그래프 연습 (1) - 인접 행렬과 인접 리스트

그래프 연습 (1) - 인접 행렬과 인접 리스트

 

해당 문제는 DFS로 진행합니다. 모든 depth를 구해봐야하므로 depth를 구할땐 depth우선 방법이 좋겠죠? 물론 최소 depth를 찾을 경우에는 BFS가 유리할 수 있습니다. 끝을 한 번 이라도 찾게되면 그 이후의 탐색은 진행하지 않아도 되기 때문입니다. (첫 발견이 최소 depth이므로)

def dfs(V, visited):
    visited[V] = True
    count = 1  # 현재 정점을 포함하여 count 시작
    
    for i in graph[V]:
        if not visited[i]:
            count += dfs(i, visited)
    
    return count

여기서 조금 복잡하게 생각했었는데, 깊이를 어떻게 다 기록을 할지에 대한 고민이었다. 처음엔 탐색이 이루어질때마다 모든 depth를 리스트로 저장해서 max()로 최종 depth를 구했는데, 그럴 필요 없이 호출되는 개수가 곧 depth이므로 위 코드와 같이 진행하였다. dfs를 다시 호출한다는 것은 깊이가 1 증가했다는 의미이고 결국 dfs를 호출한 횟수가 최종 깊이가 되는 것이다

 

visited = [False for _ in range(N+1)]
max_group_size = 0
group_id = N+1

변수 초기화

 

for i in range(1, N+1):
    if not visited[i]:
        current_group_size = dfs(i, visited)
        if current_group_size > max_group_size:
            max_group_size = current_group_size
            group_id = i
        elif current_group_size == max_group_size and i < group_id:
            group_id = i  # 동일한 크기의 그룹이 있으면 더 작은 ID를 선택

print(group_id)

서로 연결된 노드중에서 모든 노드를 탐색해야한다. 그래야 모든 그룹을 탐색할 수 있기 때문이다. 그래서 1번부터 N+1번까지 모든 노드를 탐색하게 되는데, 이때 방문이 이미 되었었다면 건너뛰는 식으로 시간을 절약했다. 

 

최종 코드

N, M = map(int, input().split())

# 인접 리스트를 사용
graph = [[] for _ in range(N+1)]
for i in range(M):
    v1, v2 = map(int, input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)
    
def dfs(V, visited):
    visited[V] = True
    count = 1  # 현재 정점을 포함하여 count 시작
    
    for i in graph[V]:
        if not visited[i]:
            count += dfs(i, visited)
    
    return count

visited = [False for _ in range(N+1)]
max_group_size = 0
group_id = N+1

for i in range(1, N+1):
    if not visited[i]:
        current_group_size = dfs(i, visited)
        if current_group_size > max_group_size:
            max_group_size = current_group_size
            group_id = i
        elif current_group_size == max_group_size and i < group_id:
            group_id = i  # 동일한 크기의 그룹이 있으면 더 작은 ID를 선택

print(group_id)

 

-끝-