코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
DFS - 줄다리기
앞서 공부한 DFS(깊이 우선 탐색)을 사용해 줄다리기 문제를 풀어보겠다.
문제
현수네 반 총 인원수는 7명입니다.
오늘은 운동회 날로 반대항 줄다리기 시합이 있습니다.
현수네 반 총 인원인 7명이 모두 줄다리기에 출전합니다.
선생님은 줄다리기를 하기 위해 7명을 일렬로 세우는데 서로 싫어하는 학생끼리 이웃하게 일렬로 세우면 경기력이 저하되어 정상적인 경기력이 나오지 않습니다.
매개변수 nums에 현수네 반 학생의 서로 싫어하는 정보가 주어지면 서로 싫어하는 학생끼리 이웃하지 않게 줄을 세우는 경우수를 알고 싶습니다.
즉 정상적인 경기력으로 줄다리기를 하기 위해 7명을 일렬로 세울 수 있는 모든 방법의 수를 구해 반환하는 프로그램을 작성하세요.
입출력 예
| nums | answer |
|---|---|
| [[1, 3], [5, 7], [4, 2]] | 1968 |
| [[3, 2], [3, 5], [5, 2], [7, 3]] | 864 |
| [[1, 2], [1, 5], [1, 7], [1, 3]] | 720 |
| [[1, 7]] | 3600 |
| [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]] | 646 |
예제 1번 설명
만약 1 2 4 3 5 6 7 로 일렬로 세운다면 2번과 4번이 서로 싫어해서 정상적인 경기력이 나오지 않습니다.
만약 1 2 3 4 5 7 6 로 일렬로 세운다면 5번과 7번이 서로 싫어해서 정상적인 경기력이 나오지 않습니다.
만약 1 2 3 4 5 6 7 로 일렬로 세운다면 서로 싫어하는 사람이 이웃하지 않아서 정상적인 경기력이 나옵니다.
제한사항
- nums의 길이는 20을 넘지 않습니다.
- 각 학생은 1번부터 7번까지 고유번호로 인식됩니다.
코드
cnt = 0
def DFS(L, nums, hates, ch):
global cnt
if L == 7:
cnt += 1
else:
for i in range(1, 8):
if nums and hates[nums[-1]][i] == 1:
continue
if ch[i] == 0:
nums.append(i)
ch[i] = 1
DFS(L+1, nums, hates, ch)
nums.pop()
ch[i] = 0
def solution(fight):
global cnt
hates = [[0]*8 for _ in range(8)]
ch = [0] * 8
for x, y in fight:
hates[x][y] = 1
hates[y][x] = 1
nums = []
cnt = 0
DFS(0, nums, hates, ch)
return cnt
print(solution([[1, 3], [5, 7], [4, 2]]))
print(solution([[3, 2], [3, 5], [5, 2], [7, 3]]))
print(solution([[1, 2], [1, 5], [1, 7], [1, 3]]))
print(solution([[1, 7]]))
print(solution([[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7]]))
풀이
-
먼저
DFS를 호출하기 전에 싫어하는 사람들을 제외하기 위한hates이차원 배열을 생성해 0으로 다 초기화시킨 후, 싫어하는 사람끼리 만나는 경우의 수를 다1로 설정해 표시해둔다. -
그 후
DFS에nums에 들어있는 원소 개수, nums, 제외할 경우의 수, 중복되지 않게 nums에 넣기 위한 ch을 넣어 호출한다. -
DFS가 호출되면 현재nums에 들어있는원소 개수(L)가 7개냐 물어본다.만족하는 경우: 싫어하는 사람들끼리 마주치지 않고 일렬로 세웠으니 경우의 수를+1한다.만족하지 않는 경우:1부터7까지자식 노드를 만든다.
만약nums가 존재하면서 싫어하는 사람끼리 만났으면 해당 노드의 자식 노드는 더 보지 않아 탐색 시간을 줄인다.
그 후,i가nums에 들어있지 않다면nums에 넣고ch에 넣었다고 표시해준다.
그리고 자식 노드i를 기준으로 또 탐색하기 위해DFS(L+1)를 호출한다. -> 레벨이 올라간다는 건 그 노드의 자식 노드를 탐색한다는 것을 의미
이렇게nums에7개의 숫자가 담기게 되면L == 7을 또 만족하므로 출력한다.
이렇게 반복하다가 중복을 허용하며 m개로 나올 수 있는 모든 순열이 출력하면 탐색을 종료한다.
