Problem Description
This problem is related to graphs, which often appear in coding tests, and it will focus on understanding friendships.
Friendships can be represented as ‘bidirectional edges’, and in this problem, we will implement an algorithm to output
the friends of a specific friend based on given friendships.
Problem
Problem Description: There are N friends. Each friend considers each other a friend, and the friendships
are given in pairs. Given these friendships, write a program that outputs the friend list of a specific friend.
However, duplicate friends should be excluded.
Input Format:
– The first line contains two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 1000).
– The next M lines consist of two integers A and B that represent the friendships.
– A and B are the numbers denoting friends, and A ≠ B always holds.
Output Format:
– Output the friend list of a specific friend K (1 ≤ K ≤ N) separated by spaces.
Example Input
5 5 1 2 1 3 2 4 3 4 4 5 3
Example Output
2 4
Problem Solving Process
Step 1: Understanding the Problem
To understand the problem, let’s think about how we can represent the given friendships.
Friendships can be represented as a graph, where ‘friends’ are ‘nodes’ and friendships are ‘edges’.
This allows us to easily find each friend’s friend list.
Step 2: Choosing a Data Structure
An ‘adjacency list’ is appropriate for representing friendships.
We can use a dictionary or an array to store each friend’s friend list.
In this problem, we will use an array with friend numbers as indices.
Step 3: Implementation
Now, let’s implement the code in Swift to solve the problem.
First, we will take the input and build an adjacency list to represent friendships, then write a program
that outputs the friend list of a specific friend K.
import Foundation
func main() {
// Input
let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let N = firstLine[0] // Number of friends
let M = firstLine[1] // Number of friendships
// Array to store friendships (adjacency list)
var friends = [[Int]](repeating: [], count: N + 1)
// Input friendships
for _ in 0..<m {="" let="" relation="readLine()!.split(separator:" "="" ").map="" int($0)!="" }="" a="relation[0]" b="relation[1]" friends[a].append(b)="" friends[b].append(a)="" k="Int(readLine()!)!" friend's="" number="" friendlist="friends[K].sorted()" print(friendlist.map="" string($0)="" }.joined(separator:="" "))="" main()="" <="" code=""></m>
<h3>Step 4: Code Explanation</h3>
<p>
The code can be divided into three main parts. The explanations for each section are as follows.
</p>
<ul>
<li>
<strong>Input and Initialization:</strong><p></p>
<ul>
<li>First, the number of friends N and the number of friendships M are read in from the first line.</li>
<li>Next, an empty array of size N+1 is created to store each friend's friend list.</li>
</ul>
</li>
<li>
<strong>Input Friendships:</strong><p></p>
<ul>
<li>The friendships are read from the next M lines and stored in the adjacency list to maintain bidirectional relationships.</li>
</ul>
</li>
<li>
<strong>Output Friend List of K:</strong><p></p>
<ul>
<li>The friend list of a specific friend K is sorted and printed, separated by spaces.</li>
</ul>
</li>
</ul>
<h2>Step 5: Testing the Code</h2>
<p>
Various input cases should be considered to test the written code.<br>
For example, let's try the following test case:
</p>
<h3>Example Input 1</h3>
<pre>5 5
1 2
1 3
2 4
3 4
4 5
3
</pre>
<h3>Example Output 1</h3>
<pre>2 4
</pre>
<h3>Example Input 2</h3>
<pre>4 4
1 2
2 3
3 4
4 1
1
</pre>
<h3>Example Output 2</h3>
<pre>2 4
</pre>
<h3>Example Input 3</h3>
<pre>4 4
1 2
3 4
2 3
1 4
2
</pre>
<h3>Example Output 3</h3>
<pre>1 3
</pre>
<h2>Conclusion</h2>
<p>
In this tutorial, we implemented an algorithm to understand friendships and output the<br>
friend list of a specific friend using Swift.<br>
Graph problems have various applications, so it's essential to practice thoroughly to enhance<br>
understanding of algorithms.
</p>
<p>
We hope you continue to improve your skills by solving more problems.
</p>
<p></p>