스위프트 코딩테스트 강좌, 친구 관계 파악하기

문제 설명

코딩테스트에서 자주 등장하는 그래프 관련 문제로, 친구 관계를 파악하는 문제를 다룰 것입니다.
친구 관계는 ‘양방향 간선’으로 표현될 수 있으며, 이 문제에서는 주어진 친구 관계를 통해
특정 친구의 친구를 출력하는 알고리즘을 구현하려고 합니다.

문제

문제 설명: N명의 친구가 있습니다. 각 친구는 서로를 친구로 간주하며,
친구 관계는 쌍으로 주어집니다. 친구 관계가 주어질 때, 특정 친구의 친구 리스트를
출력하는 프로그램을 작성하시오. 단, 중복된 친구는 제외합니다.

입력 형식:
– 첫 줄에 정수 N (1 ≤ N ≤ 100)과 정수 M (1 ≤ M ≤ 1000)이 주어집니다.
– 그 다음 M줄에 걸쳐 친구 관계를 나타내는 두 정수 A와 B로 구성됩니다.
– A와 B는 각각 친구의 번호이며, 항상 A ≠ B입니다.

출력 형식:
– 특정 친구 K (1 ≤ K ≤ N)의 친구 목록을 공백으로 구분하여 출력합니다.

예시 입력

5 5
1 2
1 3
2 4
3 4
4 5
3

예시 출력

2 4

문제 해결 과정

1단계: 문제 이해하기

문제를 이해하기 위해, 먼저 주어진 친구 관계를 어떻게 표현할 수 있을지 생각해봅니다.
친구 관계는 그래프로 표현할 수 있으며, ‘친구’는 ‘노드’로, 친구 관계는 ‘간선’으로 나타낼 수 있습니다.
이를 통해, 각 친구의 친구 목록을 쉽게 찾을 수 있습니다.

2단계: 데이터 구조 선택하기

친구 관계를 표현하기 위한 데이터 구조로는 ‘인접 리스트’가 적합합니다.
딕셔너리 또는 배열을 사용하여 각 친구의 친구 목록을 저장할 수 있습니다.
이 문제에서는 친구 번호를 인덱스로 하여 배열을 사용하겠습니다.

3단계: 구현하기

이제 문제를 해결하기 위해 스위프트(Swift) 언어로 코드를 구현해보겠습니다.
먼저 입력을 받아 친구 관계를 인접 리스트로 구축한 후, 특정 친구 K의 친구 목록을 출력하는 프로그램을 작성할 것입니다. 


import Foundation

func main() {
    // 입력 받기
    let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
    let N = firstLine[0] // 친구의 수
    let M = firstLine[1] // 친구 관계의 수
    
    // 친구 관계를 저장할 배열 (인접 리스트)
    var friends = [[Int]](repeating: [], count: N + 1)
    
    // 친구 관계 입력
    for _ in 0..

4단계: 코드 설명

코드는 크게 세 부분으로 나눌 수 있습니다. 각 부분에 대한 설명은 다음과 같습니다.

  • 입력 및 초기화:

    • 우선 첫 줄에서 친구의 수 N과 친구 관계의 수 M을 입력받습니다.
    • 그 다음, N+1 크기의 빈 배열을 생성하여 각 친구의 친구 목록을 저장합니다.
  • 친구 관계 입력:

    • 친구 관계는 주어진 M줄에 걸쳐 입력받으며, 이를 통해 양방향 관계를 인접 리스트에 저장합니다.
  • 친구 K의 친구 목록 출력:

    • 특정 친구 K의 친구 목록을 정렬한 후, 공백으로 구분하여 출력합니다.

5단계: 코드 테스트하기

작성한 코드를 테스트하기 위해 다양한 입력 케이스를 고려해야 합니다.
예를 들어, 아래와 같은 테스트 케이스를 넣어보겠습니다.

예제 입력 1

5 5
1 2
1 3
2 4
3 4
4 5
3

예제 출력 1

2 4

예제 입력 2

4 4
1 2
2 3
3 4
4 1
1

예제 출력 2

2 4

예제 입력 3

4 4
1 2
3 4
2 3
1 4
2

예제 출력 3

1 3

결론

이번 강좌에서는 스위프트를 활용하여 친구 관계를 파악하고,
특정 친구의 친구 목록을 출력하는 알고리즘을 구현했습니다.
그래프 문제는 다양한 응용이 가능하므로, 충분한 연습을 통해
알고리즘 이해도를 높이는 것이 중요합니다.

앞으로도 더 많은 문제를 풀어보며 실력을 향상시키길 바랍니다.