알고리즘

[프로그래머스] 202 프로그래머스 코드챌린지 2차 예선 - 완전범죄 - Lv.2

swanzzz 2025. 3. 20. 23:24
반응형

[오늘의 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=python3

[프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=python3)

[오늘의 학습 키워드]

  • DFS, 재귀, 백트래킹,

1. 문제설명

A 도둑과 B 도둑이 info에 담긴 모든 물건을 훔치려고 합니다.

이때 각 도둑은 물건을 훔치고 그 흔적을 남기는데 A 도둑은 n 이상 흔적을 남기면 경찰에게 걸리고

B 도둑은 m 이상 흔적을 남기면 경찰에게 걸립니다.

물건을 훔치면서 남기는 흔적은 각각 A 는 info[i][0] 이고 B는 info[i][1] 에 표시됩니다.

모든 물건을 훔칠 수 있을 때 A 도둑이 남긴 흔적의 누적 개수가 최소가 되도록 물건을 훔쳐야 합니다.

제한사항

  • 1 ≤ info의 길이 ≤ 40
    • info[i]는 물건 i를 훔칠 때 생기는 흔적의 개수를 나타내며, [A에 대한 흔적 개수, B에 대한 흔적 개수]의 형태입니다.
    • 1 ≤ 흔적 개수 ≤ 3
  • 1 ≤ n ≤ 120
  • 1 ≤ m ≤ 120

2. 접근방식

이번 문제는 혼자 힘으로 해결하지 못했습니다.

같이 모각코를 하던 형의 도움을 받아 아이디어를 얻고 문제를 해결할 수 있었습니다.

우선 결과적으로 출력해주어야 하는 것은 A가 물건을 훔친 최소한의 갯수 입니다.

그 말은 A가 물건을 훔치지 않는 경우가 제일 좋은 경우이고 그게 아닌 A가 어느정도 물건을 훔치고 B가 나머지 물건을 훔쳐 모든 물건을 훔쳐야 합니다.

그러기 위해서는 A가 물건을 훔쳤을 때와 B가 물건을 훔쳤을 때 를 기준으로 모든 경우의 수를 구해주어야 합니다.

1번 예시를 보겠습니다.

[[1,2], [2, 3], [2, 1]] 4, 4

입력이 다음과 같이 주어집니다.

info의 길이는 3이고 n과 m은 각각 4로 최대 3의 흔적을 남기며 물건을 훔칠 수 있습니다.

그렇다면 가장 좋은 방법은 1번 물건과 3번 물건을 B가 훔치고 2번 물건을 A가 훔쳐 A가 물건을 훔친 최소 흔적이 2가 되어야 합니다.

그보다 더적은 경우의 수는 없기 때문입니다.

즉, 모든 물건을 훔치는데 모든 경우의 수를 구해서 A가 가장 적게 흔적을 남기는 경우를 찾는게 이번 문제의 핵심입니다.

그러기 위해서는 DFS 탐색을 이용한 재귀 탐색을 실시하여 A가 물건을 훔친 경우의 수와 B가 물건을 훔친 경우의 수를 구해주고 그 상황에서 A가 물건을 가장 적게 훔친 경우의 수를 찾아 출력해 주어야 합니다.

자세한 설명은 코드를 통해 살펴 보겠습니다.

3. 코드

def solution(info, n, m):
    length = len(info)
    visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(length)]
    answer = float('inf')

    def DFS(info, index, n, m, length, maxN, maxM):
        nonlocal answer  # answer를 수정하기 위해 nonlocal 사용
        # 종료조건
        if index == length:
            answer = min(answer, n)
            return True

        # answer는 탐색을 통해 최솟값을 가지고 있는데 n값이 최솟값보다 커진 경우 더 이상 탐색할 필요가 없다.
        if n >= answer or visited[index][n][m]:
            return

        # 방문흔적, 다음n값과 다음m값 업데이트
        visited[index][n][m] = True
        nextN = n + info[index][0]
        nextM = m + info[index][1]

        # 탐색
        if maxN > nextN:
            DFS(info, index + 1, nextN, m, length, maxN, maxM)

        if maxM > nextM:
            DFS(info, index + 1, n, nextM, length, maxN, maxM)

    DFS(info, 0, 0, 0, length, n, m)

    if answer == float('inf'):
        return -1
    else:
        return answer

코드설명

def solution(info, n, m):
    length = len(info)
    visited = [[[False for _ in range(m)] for _ in range(n)] for _ in range(length)]
    answer = float('inf')

입력받은 info 와 n, m에 대하여 방문흔적을 남길 3차원 visited 배열을 생성해 줍니다.

해당 위치에 방문하여 물건을 훔쳤을 때 그 흔적이 최소가 되는 경우를 구하며 시간 복잡도를 줄이기 위해 방문을 실시합니다.

만약 방문처리를 하지 않는 경우 모든 경우의 수를 구해주어야 하기 때문에 시간 복잡도가 2^40으로 시간초과가 발생할 것입니다.

    def DFS(info, index, n, m, length, maxN, maxM):
        nonlocal answer  # answer를 수정하기 위해 nonlocal 사용
        # 종료조건
        if index == length:
            answer = min(answer, n)
            return True
        
        # answer는 탐색을 통해 최솟값을 가지고 있는데 n값이 최솟값보다 커진 경우 더 이상 탐색할 필요가 없다.
        if n >= answer or visited[index][n][m]:
            return
        
        # 방문흔적, 다음n값과 다음m값 업데이트
        visited[index][n][m] = True
        nextN = n + info[index][0]
        nextM = m + info[index][1]
        
        # 탐색
        if maxN > nextN:
            DFS(info, index + 1, nextN, m, length, maxN, maxM)
            
        if maxM > nextM:
            DFS(info, index + 1, n, nextM, length, maxN, maxM)

DFS 탐색을 위한 조건을 설정해 줍니다.

 

DFS 탐색시 모든 물건을 훔쳐야 하니 info의 최대인덱스 len(info) 즉 length 만큼 탐색을 실시해 줄 것입니다.

 

시작 위치는 info의 0 부터 시작하고 그때 현재 n의 누적값은 0 m의 누적값은 0 입니다.

 

또한 최대로 물건을 훔칠 수 있는 maxN과 maxM은 각각 입력받은 n과 m이 될 것입니다.

 

이제 탐색을 실시하기 위해 종료조건 먼저 설정해 주겠습니다.

 

탐색은 모든 info의 인덱스를 탐색하였을 때 종료할 것이므로 index == length와 같아지는 순간 탐색을 종료해줍니다.

이때 answer의 값은 n값과 answer값중 최소값으로 바꿔줍니다.

 

만약 탐색에 실패하여 n값이 최소값이 되지 않는다면 answer float('inf') 값이 최소값일 것입니다.

 

또한 성공적으로 탐색을 마쳤으니 탐색의 결과 True를 반환해 줍니다.

 

이제 answer를 변경하기 위한 코드를 작성해 줍니다.

 

보통 파이썬에서 함수에서 바깥의 변수에 간섭하기 위해서는 global을 사용하는데 global로 코드를 작성하여 실행하니 nameError가 발생하였고 그 원인을 찾기위해 gpt에게 물어보니 nonlocal을 사용하라는 답변을 받았습니다.

 

nonlocal로 돌려보니 돌아가서 해당 코드를 작성해 주었습니다.

 

if n >= answer or visited[index][n][m]: 

부분은 시간복잡도를 줄이기 위한 코드입니다.

 

answer값은 이미 탐색을 종료하여 최솟값을 찾았는데 다음 탐색시 answer 값보다 n값이 크다면 더이상 탐색할 이유가 없기 때문입니다.

 

또한 이미 방문한 곳은 재탐색을 실시하지 않기 위해 해당 코드를 작성해 주었습니다.

 

탐색을 실시하지 않았다면

현재 위치를 방문처리하고 nextN 과 nextM 값을 구해줍니다.

 

해당 값은 n과 m의 누적값으로 이전에 받아온 n과 m값에 현재 n과 m값을 더해 구해주었습니다.

 

그 후 다시 DFS 탐색을 실시하여 재귀함수를 실행해 줍니다.

 

당연히 탐색 위치는 다음 index가 되고 n과 m의 누적값을 최신화 하여 탐색을 실시합니다.

    DFS(info, 0, 0, 0, length, n, m)
    
    if answer == float('inf'):
        return -1
    else:
        return answer

그 결과를 얻기 위해 DFS를 시작해 줍니다.

info 배열을 넘겨주고 시작 인덱스, 누적n, 누적m, info의 길이, 최대n, 최대m 을 넘겨줍니다.

 

탐색결과 True를 반환한다면 정상적인 탐색을 실시하여 최소 n을 구한 것이고 그렇지 않은 경우 물건을 모두 훔치지 못한 경우입니다.

 

4. 결과

[회고]

알고리즘 손을 놓은지 오래되어 탐색시 방문여부를 처리하는 조건을 제대로 생각하지 못하여 어려웠던 문제입니다.

 

다른 사람들의 경우 2차원 배열과 DP를 활용하였던데 원래도 DP의 점화식을 제대로 세우지 못하여 더욱이 어려웠습니다.

 

처음 작성했던 코드는 무조건 B부터 모든 물건을 훔치고 더이상 B가 훔치지 못할 때 A가 훔치는 방향으로 작성하였는데

 

그러면 반례가 무수히 많고 A가 1번 훔치고 나머지를 B가 훔칠때 더 좋은 결과가 나올 수 있어 예제만 맞고 나머지를 틀렸던 코드입니다.

 

같이 모각코하던 형과 논의 끝에 모든 경우의 수를 구하기 위한 3차원 배열을 생성하고 그걸 DFS 탐색을 실시해 재귀로 모든 경우를 구하면 될 것같다는 결론이 나왔고 이를 통해 문제를 해결할 수 있었습니다.

 

조만간 코딩테스트를 쳐야 하는데 아직 갈길이 멀어 참담한 신경입니다...

 

더욱이 잘 풀수 있도록 알고리즘을 열심히 해야 겠습니다.

반응형