프로그래머스 완전 범죄 (C#) [Lv. 2]

프로그래머스

 

A도둑괴 B도둑이 물건을 훔치려고 합니다. 물건을 훔칠 때 생기는 흔적의 양을 배열로 받고, A도둑이 경찰에 붙잡히는 최소 흔적 개수 N과 B 도둑이 경찰에 붙잡히는 최소 흔적 M을 입력 받을 때, A와 B 모두 경찰에 붙잡히지 않으면서 모든 물건을 훔치는 경우중 A의 최소 흔적 개수를 구해주세요.

 

---

풀이 방법

info의 길이가 40이기 때문에 완전 탐색을 하면 2^40, 약 1조개의 탐색이 발생하게 됩니다.

그렇기 때문에 완전탐색으로는 문제 해결을 못할것 같지만,

예외처리를 잘해준다면 완전탐색 코드로도 충분히 해결이 가능합니다.

 

여기서는 DFS를 사용해서 문제를 풀이합니다.

---

DFS

문제를 DFS로 푼다는 것은 모든 경우의 수를 탐색한다는 것을 의미합니다.

1번 물건을 A가 훔쳤을 경우, B가 훔쳤을 경우,

1번 물건을 A가 훔치고 2번 물건도 A가 훔쳤을 경우 등

DFS에서 정의해야할 것은 A가 훔친 경우와 B가 훔친 경우가 있겠습니다.

 

public void DFS(int[,] info, int A = 0, int B = 0, int idx = 0)

A가 남긴 흔적의 개수와 B가 남긴 흔적의 개수, 현재 훔치려는 물건의 인덱스를 인자로 받게합니다.

 

bool CanA = A + info[idx, 0] < N;
bool CanB = B + info[idx, 1] < M;

if (CanB)
    DFS(info, A, B + info[idx, 1], idx + 1);
if (CanA)
    DFS(info, A + info[idx, 0], B, idx + 1);

현재 훔치려는 물건을 A와 B가 훔칠 수 있는지 체크하고, 훔칠 수 있다면 DFS를 계속 진행합니다.

 

if (idx == info.GetLength(0))
{
    answer = Math.Min(answer, A);
    return;
}

이후에 모든 물건을 훔쳤다면 반환값인 answer를 재설정 해줍니다.

 

---

시간 초과

위와 같이 DFS를 정의한다면 시간초과가 발생하게 됩니다.

그렇기 때문에 예외처리를 추가해줄 필요가 있습니다.

 

1. 정답과 비교하기

if (A >= answer)
    return;

A가 남긴 흔적의 개수가 answer보다 많다면 더 이상 정답이 될 수 없기 때문에 DFS를 종료합니다.

 

 

2. 이미 같은 경우를 계산한적 있는지 찾기

HashSet<(int, int, int)> visited = new HashSet<(int, int, int)>();

HashSet으로 A의 흔적, B의 흔적, 훔치려는 물건의 Index를 저장합니다.

 

if (A >= answer || visited.Contains((A, B, idx)))
    return;

visited.Add((A, B, idx));

이후에 이미 같은 상황이 있었다면 DFS를 종료하고

그런 상황이 없었다면, HashSet에 현재 상황을 기록합니다.

 

해당 코드는 순차적으로 물건을 훔치기 때문에, 이전에 어떤 물건을 누가 훔쳤는지와는 관계 없이

현재의 상황이 같다면, 다음 계산도 같은 결과를 불러오게 됩니다.

때문에 중복 계산을 회피하는 코드라고 보면 되겠습니다.

 

---

 

정답 코드

using System;
using System.Collections.Generic;

public class Solution 
{
    int answer = Int32.MaxValue;
    int N, M;
    
    HashSet<(int, int, int)> visited = new HashSet<(int, int, int)>();
        
    public void DFS(int[,] info, int A = 0, int B = 0, int idx = 0)
    {
        if (A >= answer || visited.Contains((A, B, idx)))
            return;
        
        visited.Add((A, B, idx));
        
        if (idx == info.GetLength(0))
        {
            answer = Math.Min(answer, A);
            return;
        }
        
        bool CanA = A + info[idx, 0] < N;
        bool CanB = B + info[idx, 1] < M;
        
        if (CanB)
            DFS(info, A, B + info[idx, 1], idx + 1);
        if (CanA)
            DFS(info, A + info[idx, 0], B, idx + 1);
    }
    
    public int solution(int[,] info, int n, int m) 
    {
        int size = info.GetLength(0);
        N = n;
        M = m;

        DFS(info);

        return answer == Int32.MaxValue ? -1 : answer;
    }
}

 

 

---

결과