문제 설명
어떤 날의 거리에서 시작해 특정 지점으로 이동하는 도중에 여러 사람과의 대화에서 서로 다른 상태를 가진 사람들로부터 이야기를 듣게 된다.
이 사람들은 각각 사실과 거짓을 말할 수 있으며, 우리는 모두가 말하는 내용을 바탕으로 진실을 파악해야 한다.
주어진 데이터에 따라 자신의 위치를 결정하는 알고리즘을 구현하라.
문제 정의
N명이 있는 사람들 중, 각 사람이 자신이 아는 것에 대해 진실 또는 거짓을 말할 수 있다.
각 사람은 다른 사람의 정보에 따라 자신의 진실성을 정할 수 있어야 한다.
주어진 대화 정보를 바탕으로 특정 지점에서 진실을 이야기할 수 있는 가능한 인물의 수를 계산하라.
입력 형식
- 첫 번째 줄에 사람의 수 N이 주어진다.
- 두 번째 줄에는 사람들 간의 대화 정보가 주어진다. 각 정보는 “A B T/F” 형식으로, A는 정보 제공자, B는 정보 수신자, T는 진실, F는 거짓을 의미한다.
출력 형식
진실을 말할 수 있는 사람들의 총 수를 출력하라.
문제 풀이 강좌
1. 문제 이해
문제를 이해하기 위해, 먼저 제공되는 데이터의 의미를 분석해보자.
사람들은 서로 대화를 하며, A가 B에게 알리는 정보가 진실인지 거짓인지에 대한 명확한 규칙을 정해야 한다.
이럴 경우, 우리는 이 정보들을 그래프로 나타내고 DFS 또는 BFS와 같은 알고리즘을 활용하여 진실성을 판단할 수 있다.
2. 알고리즘 설계
정보의 전달 관계를 위한 그래프를 만들고, 대화 속에서 발생할 수 있는 모든 진실과 거짓의 경우의 수를 따져보아야 한다.
DFS (Depth First Search) 알고리즘을 이용하여, 각 사람을 따라가며 진실과 거짓을 전파하는 과정은 다음과 같다.
3. C# 코드 구현
using System;
using System.Collections.Generic;
class Program
{
static void Main(string[] args)
{
// 입력 받기
int N = int.Parse(Console.ReadLine());
List> conversations = new List>();
string line;
while ((line = Console.ReadLine()) != null && line.Length > 0)
{
var parts = line.Split(' ');
int A = int.Parse(parts[0]);
int B = int.Parse(parts[1]);
bool isTruth = parts[2].Equals("T");
conversations.Add(new Tuple(A, B, isTruth));
}
// 그래프 형성
Dictionary>> graph = new Dictionary>>();
foreach (var convo in conversations)
{
if (!graph.ContainsKey(convo.Item1))
graph[convo.Item1] = new List>();
graph[convo.Item1].Add(new Tuple(convo.Item2, convo.Item3));
}
// DFS 실행
HashSet visited = new HashSet();
int truthfulCount = 0;
void DFS(int person)
{
if (visited.Contains(person)) return;
visited.Add(person);
truthfulCount++;
if (graph.ContainsKey(person))
{
foreach (var neighbor in graph[person])
{
if (neighbor.Item2) // 진실을 말하는 경우
DFS(neighbor.Item1);
}
}
}
foreach (var person in graph.Keys)
{
if (!visited.Contains(person))
{
DFS(person);
}
}
// 결과 출력
Console.WriteLine(truthfulCount);
}
}
4. 코드 설명
위의 C# 코드는 간단한 DFS 알고리즘을 활용하여 문제를 해결하는 방법을 보여준다.
먼저, 입력을 받고 사람들 간의 대화 정보로 그래프를 구성한다.
이후 각 사람에 대해 DFS를 실행하여, 진실을 말할 수 있는 사람의 수를 계산하고 그 결과를 출력한다.
5. 시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(V + E)이다.
여기서 V는 사람의 수, E는 대화의 수를 의미한다.
즉, 그래프의 모든 정점과 간선을 탐색하는 시간이 소요되기 때문에, 대체로 효율적이라고 볼 수 있다.
6. 코드 개선과 최적화
추가로 이 문제에서 최적화를 고려할 수 있는 방법으로는, DFS 대신 BFS를 사용할 수도 있다.
또한, 메모이제이션을 도입하여 이미 확인한 진실과 거짓의 결과를 저장해두면
향후 동일한 요청에 대해 빠르게 결과를 반환할 수 있다.
결론
이 강좌에서는 C#을 이용하여 주어진 문제를 해결하기 위한 알고리즘을 구축하고 이를 구현하는 방법을 알아보았다.
그래프 알고리즘과 DFS를 활용해 진실을 이야기할 수 있는 인물 수를 계산하는 과정을 통해
실제 코딩테스트에서 유용한 접근 방식을 익히게 되었다.
문제 해결 능력을 키우기 위해 다양한 문제 유형을 연습하고, 알고리즘에 대한 이해도를 높이는데 도움이 되길 바란다.