백준 C# - 1753 +) 풀이 단계 설명

우선순위 큐로 많이 푸는 것 같은데 일단 그래프로 풀어지나? 하고 풀어봤더니 통과가 됐다!

문제는 다익스트라를 이용해야하는 문제였다.

 

푸는 순서

1. Edge 클래스

간선 정보를 담기 위한 클래스이다.

class Edge
{
    public int To { get; }
    public int Weight { get; }

    public Edge(int to, int weight)
    {
        To = to; // 간선의 도착 정점
        Weight = weight; // 간선의 가중치
    }
}

---

2. 그래프 만들기

01 정점, 간선 갯수 입력 받기

string[] input = Console.ReadLine().Split();
int v = int.Parse(input[0]); // 정점의 개수
int e = int.Parse(input[1]); // 간선의 개수

---

02 List<List<Edge>>

각 리스트는 그래프의 정점과 해당 정점과 연결된 간선 정보를 저장한다.

List<List<Edge>> graph = new List<List<Edge>>();

 

---

03 각 정점에 빈 리스트 할당

for (int i = 0; i <= v; i++)
{
    graph.Add(new List<Edge>());
}

graph 리스트의 초기화 결과

graph[0] -> []
graph[1] -> []
graph[2] -> []
.. v 크기만큼

---

04 시작 정점 입력받기

int startVertex = int.Parse(Console.ReadLine());

---

05 graph 채워 넣기

for (int i = 0; i < e; i++)
{
    input = Console.ReadLine().Split();
    int from = int.Parse(input[0]);
    int to = int.Parse(input[1]);
    int weight = int.Parse(input[2]);
    graph[from].Add(new Edge(to, weight));
}

graph 리스트의 예시 결과

graph[0] -> [Edge(1, 2), Edge(2, 3)] 
graph[1] -> [Edge(0, 2), Edge(2, 1), Edge(3, 3)]  
graph[2] -> [Edge(0, 1), Edge(1, 1), Edge(3, 1)]
graph[3] -> [Edge(1, 3), Edge(2, 1)]

---

05 거리및 방문 배열 초기화

int[] distance = new int[v + 1]; // v + 1인 이유는 정점 번호가 1부터 시작하는 경우가 많기 때문
Array.Fill(distance, Int32.MaxValue); // 모든 정점까지의 거리 무한대로 설정
distance[startVertex] = 0; // 시작 정점으로부터 초기 거리는 0으로 설정
bool[] visited = new bool[v + 1]; // 정점의 방문 여부

---

3. 다익스트라 알고리즘

코드 전문

for (int i = 0; i < v - 1; i++)
{
    int minDistance = int.MaxValue;
    int currentVertex = 0;

    // 방문하지 않은 정점 중에서 최단 거리의 정점 선택
    for (int j = 1; j <= v; j++)
    {
        if (!visited[j] && distance[j] < minDistance)
        {
            minDistance = distance[j];
            currentVertex = j;
        }
    }

    visited[currentVertex] = true;

    // 선택된 정점을 통해 갈 수 있는 다른 정점들의 최단 거리 갱신
    foreach (Edge edge in graph[currentVertex])
    {
        if (!visited[edge.To] && distance[currentVertex] != int.MaxValue)
        {
            int newDistance = distance[currentVertex] + edge.Weight;
            if (newDistance < distance[edge.To])
            {
                distance[edge.To] = newDistance;
            }
        }
    }
}

01 모든 정점 방문 반복문

반복 횟수가 v - 1인 이유는 시작 정점을 제외한 모든 정점이여야하기 때문이다.

for (int i = 0; i < v - 1; i++)

02 현재까지 발견한 최단거리와 그에 해당하는 정점 변수 초기화

int minDistance = int.MaxValue;
int currentVertex = 0;

03 방문하지 않은 정점 중에서 최단 거리의 정점 선택

for (int j = 1; j <= v; j++)
{
    // 현재 정점 j가 방문하지 않은 상태이고 현재까지 발견한 최단 거리보다 정점j까지 거리가 짧을때
    if (!visited[j] && distance[j] < minDistance) 
    {
        minDistance = distance[j]; // 현재까지 발견한 최단 거리 업데이트
        currentVertex = j; // 선택된 정점 J의 번호를 currentVertext에 저장
    }
}

04 최단 거리를 가지는 정점 방문했다고 표시

visited[currentVertex] = true;

05 currentVertex을 기반으로 인접한 정점들의 최단 거리 업데이트

foreach (Edge edge in graph[currentVertex]) // 현재 선택된 정점과 연결된 모든 간선에대해 반복
{
    // 방문하지 않았거나 현재의 최단 거리가 MaxValue인 경우에만 실행
    if (!visited[edge.To] && distance[currentVertex] != int.MaxValue)
    {
        // 현재까지의 최단거리 + 현재 간선의 가중치를 더해 새로운 거리를 계산
        int newDistance = distance[currentVertex] + edge.Weight;
        // 새로 계산한 거리가 기존에 알고있던 해당 정점까지의 최단 거리보다 작다면 업데이트
        if (newDistance < distance[edge.To])
        {
            distance[edge.To] = newDistance;
        }
    }
}

---

4. 출력

만약 시간초과가 뜬다면 출력 부분을 StringBuilder로 고치고 다시 제출해보자

StringBuilder sb = new StringBuilder();
for (int i = 1; i <= v; i++) // 정점 번호가 1부터이므로 i = 1이어야 한다.
{
    if (distance[i] == Int32.MaxValue)
    {
        sb.AppendLine("INF");
    }
    else
    {
        sb.AppendLine(distance[i].ToString());
    }
}
Console.WriteLine(sb.ToString());

---

예시 문제

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

과정

---

코드 전문

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace baek2
{
    class Program
    {
        class Edge
        {
            public int To { get; }
            public int Weight { get; }

            public Edge(int to, int weight)
            {
                To = to;
                Weight = weight;
            }
        }
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split();
            int v = int.Parse(input[0]); 
            int e = int.Parse(input[1]); 

            List<List<Edge>> graph = new List<List<Edge>>();
            for (int i = 0; i <= v; i++)
            {
                graph.Add(new List<Edge>());
            }

            int startVertex = int.Parse(Console.ReadLine());

            // 그래프 정보 입력
            for (int i = 0; i < e; i++)
            {
                input = Console.ReadLine().Split();
                int from = int.Parse(input[0]);
                int to = int.Parse(input[1]);
                int weight = int.Parse(input[2]);
                graph[from].Add(new Edge(to, weight));
            }

            int[] distance = new int[v + 1];
            Array.Fill(distance, Int32.MaxValue);

            distance[startVertex] = 0;
            bool[] visited = new bool[v + 1];

            for (int i = 0; i < v - 1; i++)
            {
                int minDistance = int.MaxValue;
                int currentVertex = 0;
                Console.WriteLine($"currentVertex {currentVertex}");
               
                for (int j = 1; j <= v; j++)
                {
                    if (!visited[j] && distance[j] < minDistance)
                    {
                        minDistance = distance[j];
                        currentVertex = j;
                    }
                }
             
                visited[currentVertex] = true;

                foreach (Edge edge in graph[currentVertex])
                {
                    if (!visited[edge.To] && distance[currentVertex] != int.MaxValue)
                    {
                        int newDistance = distance[currentVertex] + edge.Weight;
                        if (newDistance < distance[edge.To])
                        {
                            distance[edge.To] = newDistance;
                        }
                    }
                }
            }

            StringBuilder sb = new StringBuilder();
            for (int i = 1; i <= v; i++)
            {
                if (distance[i] == Int32.MaxValue)
                {
                    sb.AppendLine("INF");
                }
                else
                {
                    sb.AppendLine(distance[i].ToString());
                }
            }
            Console.WriteLine(sb.ToString());
        }
    }

    
}