프로그래머스 혼자 놀기의 달인 문제 풀이(Python, 완전탐색, DFS, LV2)

프로그래머스 혼자 놀기의 달인 문제 바로가기

문제 접근

문제에서 열려있는 상자를 만나면 종료, 상자안에 다음 상자의 번호가 들어있음이라는 조건들을 보고 완전탐색으로 확인하고 가장 큰 그룹 두개의 개수를 곱하면 될 것으로 생각하고 문제를 풀었다.

문제 풀이

완전탐색 DFS

완전탐색을 DFS로 구현했다. 현재 상자를 확인하고 안에 든 번호가 다음 상자이다.
다음 상자의 방문 여부를 확인한 후에 방문 했었다면 탐색을 종료하고 지금까지 센 숫자를 return한다. 만약 방문하지 않았더라면 stack에 번호를 추가하여 반복문을 계속 진행하는 방식으로 진행했다.

def choice(i):
	stack = []
	stack.append(i)
	cnt = 0
	while stack:
		box = stack.pop() # 깔 상자번호
		cnt += 1
		visited[box] = True
		next_box = cards[box] # 다음에 깔 상자 번호
		if visited[next_box] == False:
			stack.append(next_box)
        else:
			return cnt

최댓값

result에 그룹들의 상자 개수가 들어가 있다.
이 리스트를 정렬하여 가장 큰 두개의 값을 곱한 값을 return하면 정답이다.

	for i in range(1, N):
        if visited[i] == False:
            res = choice(i)
            if res == N-1:
                return 0
            result.append(res)
result.sort()    
return result[-1] * result[-2]

그룹이 하나일때 조건처리

그룹이 하나라면 0을 return하라는 조건이 있었다.
따라서 res의 값이 N-1이라면 모든 상자를 돌았다는게 되고 그 뜻은 그룹이 하나라는 뜻이다. 따라서 return 0를 통해서 0을 return해 종료했다.

for i in range(1, N):
        if visited[i] == False:
            res = choice(i)
            if res == N-1:
                return 0
            result.append(res)

제출 코드

from collections import deque
def solution(cards):
    answer = 0
    cards = deque(cards)
    cards.appendleft(0)
    # n이하의 카드들
    # 1~n까지 상자들
    # 상자열고 숫자 확인하고 그 숫자에 해당하는 번호를 가진 상자를 열어감
    # 열려있는 상자를 만나면 종료
    # 이게 1번 그룹
    def choice(i):
        stack = []
        stack.append(i)
        cnt = 0
        while stack:
            box = stack.pop() # 깔 상자번호
            cnt += 1
            visited[box] = True
            next_box = cards[box] # 다음에 깔 상자 번호
            if visited[next_box] == False:
                stack.append(next_box)
            else:
                return cnt
    N = len(cards)
    visited = [False for i in range(N)]
    result = []
    for i in range(1, N):
        if visited[i] == False:
            res = choice(i)
            if res == N-1:
                return 0
            result.append(res)
    
    result.sort()    
    return result[-1] * result[-2]