[프로그래머스] 배달 문제 풀이 C# 코딩테스트

문제 링크 : programmers.co.kr/learn/courses/30/lessons/12978

 

문제 이해 후 DFS를 생각하고 구현

public int solution(int N, int[,] road, int K)
{
    var visitedVillages = new Dictionary<int, int>();

    dfs(road, 1, visitedVillages, K);

    return visitedVillages.Count();
}

 

방문 기록용 Dictionary<int, int> 생성.

<마을 번호, 갈 수 있는 남은 거리>를 기록한다.

처음엔 <마을번호, 방문 여부>만 <int, bool> type으로 기록하려 했지만 특정 마을(V)을 한번 방문했다는 이유로 검사하지 않으면 이후에 나오는 더 짧은 거리로 인해 V를 통해 갈 수 있는 마을들을 체크하지 못할 수 있으므로 남은 거리를 기록하도록 수정했다.

 

private void dfs(int[,] road, int village, Dictionary<int, int> visitedVillage, int capa)
{
    // 방문처리, 갈수있는 거리 업데이트
    if (visitedVillage.TryGetValue(village, out var maxCapa))
    {
        if (maxCapa < capa)
        	visitedVillage[village] = capa;
        else
        	return;
    }
    else
    {
        visitedVillage.Add(village, capa);
    }

    //연결된 마을들에 대해 capa가 충분하다면 방문
    for (int i = 0; i < road.GetLength(0); i++)
    {
    	int nextVillage;

        if (road[i, 0].Equals(village))
        	nextVillage = road[i, 1];
        else if (road[i, 1].Equals(village))
        	nextVillage = road[i, 0];
        else
        	continue;

        capa -= road[i, 2];

        if (capa >= 0)
        	dfs(road, nextVillage, visitedVillage, capa);

        capa += road[i, 2];
    }
}