13023번: ABCDE / gold 5 / 백트래킹

https://www.acmicpc.net/problem/13023

13023번: ABCDE

'''
13023번: ABCDE / gold 5 / 백트래킹
'''
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**8)


# 백트래킹을 이용한 친구 관계 확인
def check_friend(s):
    # 조건에 맞는 친구 관계 있을 시 / 종료조건
    if len(visited) == 5:
        print(1)
        exit()
    for next in relation[s]:
        if next not in visited:
            visited.add(next)
            check_friend(next)
            visited.remove(next)


# 입력받기
N, M = map(int, input().split())
relation = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    relation[x].append(y)
    relation[y].append(x)
# 0~N-1 친구까지 확인하기
start = 0
end = N - 1
while start <= end:
    visited = set()
    check_friend(start)
    start += 1
print(0)

코드 리뷰

- 해당 문제를 풀고 정답 판정을 받을때 까지 약 35분 소요되었습니다.

 

(1) 처음에 틀렸던 부분은 A->B->C->D->E 친구관계 조건. 

- 5번만! 친구관계가 이어지기만 하면 됨 (모든 N 친구들이 친구관계가 이어져야 된다 처음에 생각해 틀렸습니다)

 

(2) 중복된 친구관계를 나타내는 것을 방지 하기 위한 visited 

- visited 를 통해서 이미 선택한 친구 번호는 중복 선택이 되지 않게 설정 (ex / A->B->A->...)

- 처음 visited 를 만들 시, visited = [0 for _ in range(N)] 으로 선언해 활용 했더니 메모리 초과나, 시간 초과가 발생했습니다.

- 따라서, visited를 set()로 선언하고, 선택된 친구 번호를 넣는 작업을 함으로서 문제를 해결했습니다.