114. (중요)배달 (튜플(Tuple), Custom Class)
기본 틀 :
using System;
class Solution
{
public int solution(int N, int[,] road, int K)
{
int answer = 0;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
System.Console.WriteLine("Hello C#");
return answer;
}
}
해당 문제를 풀면서 많은 생각을 했기 때문에 기억에 오래 남을 것 같다.
첫 번째 생각) 처음 생각한 것은 자료형이었다.
저번에 아래의 문제를 풀면서 값 튜플(Value Tuple)이라는 문법에 대해 알게 돼
https://kagan-draca.tistory.com/456
110. 두 큐 합 같게 만들기
기본 틀 : using System;public class Solution { public int solution(int[] queue1, int[] queue2) { int answer = -2; return answer; }} 처음에는 간단하게 Queue로 요소를 저장하고 sum1 = queue1.Sum()과 sum2 = queue2.Sum()로 합을 저장한
kagan-draca.tistory.com
값 튜플(Value Tuple)을 사용해서 point - point 정보와 비용을 저장하고자 시도 했다.
그래서,
Dictionary<int, List<(int point, int cost)>> test = new Dictionary<int, List<(int,int)>>();
위와 같은 자료형을 만들어 Key에 Point, Value에 Point와 비용을 저장하고 시도했다.
error CS1525: Unexpected symbol `,', expecting `.'
error CS1031: Type expected
error CS1031: Type expected
그런데 위와 같은 타입 오류가 발생하기 시작했다.
오류 발생 원인을 찾아보니 해당 문법은 C# 7.0 이상부터 사용이 가능한 문법으로
프로그래머스 Level 2 배달 문제는 C# 버전이 7.0 이상이 아니라서 사용할 수 없었다.
그래서, 튜플(Tuple)의 사용 방법을 좀 더 찾아보기 시작했다.
그 결과 C# 4.0 문법으로
// 자료 구조 생성
Dictionary<int, List<Tuple<int, int>>> test = new Dictionary<int, List<Tuple<int, int>>>();
test = new List<Tuple<int, int>>();
// 자료 삽입
test[정수형 키 값].Add(new Tuple<int, int>(2, 5))
or
test[정수형 키 값].Add(Tuple.Create(2, 5)))
// 자료 탐색
foreach(var entity in dict)
{
foreach(var item in entity.Value)
{
Console.WriteLine("Item1 : "+item.Item1+", Item2 : "+item.Item2);
}
}
으로 튜플(Tuple)을 사용할 수 있었다.
위의 문법 처럼 사용할려고 하니 item.Item1, item.Item2 같이 값이 명확하지 않은 부분이 마음에 들지 않아
public class Value
{
public int Point { set; get; }
public int Cost { set; get; }
public Value(int point, int cost)
{
this.Point = point;
this.Cost = cost;
}
}
튜플(Tuple)을 사용하는 대신 Class를 직접 만들기로 결정했다.
위의 클래스를 사용하기 위해서는 자료 구조를
Dictionary<int, List<Value>> dict = new Dictionary<int, List<Value>>();
위와 같이 선언해주면 되고
for(int i = 0; i < road.GetLength(0); i++)
{
int point1 = road[i, 0], point2 = road[i, 1], cost = road[i, 2];
if(!dict.ContainsKey(point1)) dict[point1] = new List<Value>();
dict[point1].Add(new Value(point2, cost));
if(!dict.ContainsKey(point2)) dict[point2] = new List<Value>();
dict[point2].Add(new Value(point1, cost));
}
각각의 지점과 비용을 저장할 수 있었다.
두 번째 생각) 다음으로는 'Dictionary를 BFS, DFS 어떤 방식으로 탐색하는가' 였다.
해당 문제는 'BFS로 푸는 것이 최소 비용 경로를 찾는 측면에서 더 좋은 성능'을 보일 것이라 생각과
'DFS로 풀면 재미있지 않을까 + 익숙한게 DFS인데' 라는 생각 사이에서 고민을 했다.
결국, 재미있어 보이는 DFS로 문제를 풀어보기 시작했다.
DFS를 재귀 방식으로 풀 계획이라 필요한 매개변수를 작성해본 결과
// 필요한 매개변수
// 길 연결 정보 dictionary
// 방문 여부
// 현재 위치
// 제한 비용
// 현재 비용
public void DFS(Dictionary<int, List<Value>> dict, bool[] visited, int currentPoint, int K, int currentCost)
{
}
위와 같은 매개변수들이 필요할 것이라 판단 했고 반환형은 없는 것으로 설정했다.
반환형이 없을 때에는
int count
or
List<int> list = new List<int>()
list.Count;
or
// 해당 자료형을 향후 선택
// 이유는 아래에 나옴
HashSet<int> list = new HashSet<int>();
list.Count;
셋 중 하나의 필드를 작성해서 향후 count를 구할 수 있다.
기본적인 DFS의 방문 여부를 바탕으로 한 point - point 코드를 작성하고
public void DFS(Dictionary<int, List<Value>> dict, bool[] visited, int currentPoint, int K, int currentCost)
{
if(!visited[currentPoint] && currentCost <= K)
{
visited[currentPoint] = true;
list.Add(currentPoint);
foreach(var next in dict[currentPoint])
{
DFS(dict, visited, next.Point, K, currentCost + next.Cost);
}
visited[currentPoint] = false;
}
}
비용을 비교하는 코드를 추가하고 채점을 시작해봤다.
그 결과, 예상은 했지만
테스트 32(다른 테스트는 모두 통과)에서 "시간 초과"가 발생했다.
해당 원인으로는 현재 point를 방문한 이후 다음 point 탐색을 위해
visited[currentPoint] = false
방문 여부를 false로 바꾸기 때문에 연결된 모든 point를 탐색하는 방식이라
"시간 초과"가 발생할 수 밖에 없는 환경이었다.
또한, 중복으로 방문을 진행하기 때문에 count를 구하는 코드는
HashSet<int> list = new HashSet<int>();
list.Count;
HashSet이 돼어야만 한다.
세 번째 생각) '이 상황에서 어떻게 중복 방문을 없애고 최단 비용 탐색을 진행할 것인가'를 생각해봤다.
그리고 문제와 제공되는 매개변수들을 바탕으로
'배달은 모두 1(point)에서 다른 point 까지 가능 여부'
(시작점이 정해져 있는 문제)
+
' 1 - 직접 연결 안 된 point 까지의 최소 비용'
(임의의 다리가 있다고 판단하에 최소 비용)
으로 최소 비용을 구하는 과정과 탐색을 한 번에 진행시켜
최소 비용이 아닌 경우는 탐색이 진행되지 않도록 하면 된다는 판단을 했다.
그래서,
// 시작 지점(1) - 원하는 지점 비용 저장
// 가상의 다리가 있는 것 처럼 만들기
int[] startToPointCost = new int[N + 1];
startToPointCost[1] = 0;
for(int i = 2; i < startToPointCost.Length; i++)
{
startToPointCost[i] = int.MaxValue;
}
위와 같이 1 - point(1제외 다른 point) 까지의 비용을 저장할 정수형 배열을 선언해주고
해당 비용을 1을 제외한 다른 지점까지의 모든 비용을 int형의 최고값으로 설정한 후
// 필요한 매개변수
// 길 연결 정보 dictionary
// 방문 여부
// 현재 위치
// 시작 - 해당 위치(가상의 다리) 최소 비용 (추가된 매개변수)
// 제한 비용
// 현재 비용
public void DFS(Dictionary<int, List<Value>> dict, bool[] visited, int currentPoint, int[] startToPointCost, int K, int currentCost)
{
if(!visited[currentPoint] && currentCost <= K)
{
visited[currentPoint] = true;
list.Add(currentPoint);
foreach(var next in dict[currentPoint])
{
// 추가된 if문
if((currentCost + next.Cost) <= startToPointCost[next.Point])
{
// 최단 경로 비용 갱신
startToPointCost[next.Point] = currentCost + next.Cost;
DFS(dict, visited, next.Point, startToPointCost, K, currentCost + next.Cost);
}
}
visited[currentPoint] = false;
}
}
DFS를 위와 같이 수정해 문제를 해결할 수 있었다.
여담)
위의 문제는 BFS를 활용해서 다익스트라 알고리즘을 구현해 푸는 것이 정석으로 보이지만
해당 문제의 특수성
(
'배달은 모두 1(point)에서 다른 point 까지 가능 여부'
(시작점이 정해져 있는 문제)
)
으로 약간의 코드 수정을 통해 해결할 수 있었던 것 같다.
전체 코드 :
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
class Solution
{
// point to point 비용 저장
public class Value
{
public int Point { set; get; }
public int Cost { set; get; }
public Value(int point, int cost)
{
this.Point = point;
this.Cost = cost;
}
}
public HashSet<int> list = new HashSet<int>();
public int solution(int N, int[,] road, int K)
{
Dictionary<int, List<Value>> dict = new Dictionary<int, List<Value>>();
// 시작 지점(1) - 원하는 지점 비용 저장
// 가상의 다리가 있는 것 처럼 만들기
int[] startToPointCost = new int[N + 1];
startToPointCost[1] = 0;
for(int i = 2; i < startToPointCost.Length; i++)
{
startToPointCost[i] = int.MaxValue;
}
for(int i = 0; i < road.GetLength(0); i++)
{
int point1 = road[i, 0], point2 = road[i, 1], cost = road[i, 2];
if(!dict.ContainsKey(point1)) dict[point1] = new List<Value>();
dict[point1].Add(new Value(point2, cost));
if(!dict.ContainsKey(point2)) dict[point2] = new List<Value>();
dict[point2].Add(new Value(point1, cost));
}
bool[] visited = new bool[N + 1];
DFS(dict, visited, 1, startToPointCost, K, 0);
// 개수 구하기
return list.Count;
}
// 필요한 매개변수
// 길 연결 정보 dictionary
// 방문 여부
// 현재 위치
// 시작 - 해당 위치(가상의 다리) 최소 비용
// 제한 비용
// 현재 비용
public void DFS(Dictionary<int, List<Value>> dict, bool[] visited, int currentPoint, int[] startToPointCost, int K, int currentCost)
{
if(!visited[currentPoint] && currentCost <= K)
{
visited[currentPoint] = true;
list.Add(currentPoint);
foreach(var next in dict[currentPoint])
{
if((currentCost + next.Cost) <= startToPointCost[next.Point])
{
startToPointCost[next.Point] = currentCost + next.Cost;
DFS(dict, visited, next.Point, startToPointCost, K, currentCost + next.Cost);
}
}
visited[currentPoint] = false;
}
}
}