https://school.programmers.co.kr/learn/courses/30/lessons/92343
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
from collections import deque
def solution(info, edges):
visit = [0 for i in range(len(info))]
graph = [[] for i in range(len(info))]
for edge in edges:
graph[edge[0]].append(edge[1])
visit[0] = 1
d = deque([[0, [1,0], visit]])
ans = 0
while d:
current = d.popleft()
idx,sheepNwolf, v = current[0], current[1], current[2]
#현재 늑대가 양보다 같거나 같으면 종료
if sheepNwolf[0] <= sheepNwolf[1]:
continue
if sheepNwolf[0] > ans:
ans = sheepNwolf[0]
#다음 노드로 갈수 없으면 종료
for next_idx in graph[idx]:
if next_idx == []:
break
#다음 노드가 존재하면
if v[next_idx] == 0:
new_v = v[:]
new_v[next_idx] = 1
#check 값 경신
snf = [0,0]
for i in range(len(info)):
if new_v[i] == 1:
if info[i] == 0:
snf[0] +=1
else:
snf[1] +=1
d.append([0, snf, new_v])
else:
d.append([next_idx, sheepNwolf, v])
return ans
문제 정리
위의 그림처럼 양과 늑대가 있는 이진트리가 있다.
가장 부모 노드인 0은 항상 양이며 시작 지점이다.
자식 노드로 가면서 양과 늑대가 추가되며, 항상 양은 늑대보다 많아야 한다.
지나갔던 노드로 다시 돌아갈 수 있으며, 얻을 수 있는 최대의 양의 개수를 구해라!
문제 접근 사고 과정
초반에는 기존의 DFS처럼 지나가면서 양과 늑대의 수를 비교하는 문제인 줄 알았다.
하지만, 문제 조건에서 갔던 길을 다시 돌아가서, 다른 길로 방문할 수 있다.
즉, 기존처럼 갔던 길을 다시 돌아가지 않으며 (노빠꾸로..), 경우의 수를 줄이는 방법은 맞지 않다는 것이다.
고민 끝에, 결국 매 시도마다 0번 노드 (첫 번째 노드)로 돌아가야 한다는 생각을 하게 되었다..
문제 조건 중에, 노드의 개수는 1에서 17개로 정해져 있다.
즉, 아무리 많아도 17개의 노드만 존재하다는 것이다.
가능한 경우의 수가 많지 않기 때문에, 매 시도마다 처음으로 돌아가서 그래프를 돌아도 된다는 생각을 하게 되었다.
추가로 문제가 요구하는 제한사항은 양과 늑대의 수의 비교이다.
즉 문제 해결 과정을 설명하면..?
1. 현재 위치와, 양과 늑대, 방문한 정보를 얻는다.
2. 양과 늑대의 수를 비교하며, 양이 적으면, 제외시킨다.
3. 방문하지 않았던 노드로 방문하여, 방문처리해준다.
위 세가지 순서를 반복하면 된다!
[프로그래머스] 여행경로 [Level 3] (python 파이썬) [BFS]
https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는
mail-study.tistory.com
위의 DFS 설명을 보면 DFS 문제의 사고과정은 이러하다.
DFS 문제의 사고과정
입력의 제한조건을 잘 보며 모든 경우를 다 살펴봐도 시간복잡도가 초과될지 생각해보자!
문제가 어떤 정답을 요구하는 가에 따라 어떤 식으로 방문 처리를 해야 할 지 생각해보자!
문제가 요구하는 핵심적인 로직을 어떻게 쉽게 짤 지 고민해보자!
차근차근 알아보자!
1. 입력의 제한조건을 잘 보며 모든 경우를 다 살펴봐도 시간복잡도가 초과될지 생각해보자!
앞서 설명했듯이 시간복잡도가 초과되지 않는다.
2. 문제가 어떤 정답을 요구하는 가에 따라 어떤 식으로 방문 처리를 해야 할 지 생각해보자!
그래프가 이진 트리이므로, for문을 돌며 최대 2개의 자식 노드를 방문할 것이다.
이때, 첫 번째 자식 노드에서 방문 처리를 한 상태로, 두 번째 자식 노드를 방문하면,
첫 번째 자식을 방문하지 않고, 두 번째 자식 노드를 방문하는 경우는 고려할 수 없게 된다.
for문을 돌며 자식을 순서대로 돌기 때문에, 순서에 영향을 받게 된다는 것이다.
즉, 자식 노드에 방문 처리를 할 때는 현재 까지의 방문 정보를 복사해 새로운 방문 정보를 만든 후 경신해야 한다.
3. 문제가 요구하는 핵심적인 로직을 어떻게 쉽게 짤 지 고민해보자!
앞서 설명했듯이, 자식 노드에 처음 방문한 경우라면, 방문 처리를 해준 뒤, 0번 노드로 되돌아갔다.
덱에서는 다음과 같은 정보가 들어있다
| 현재 노드 위치 | 현재까지 방문한 노드의 양과 늑대의 수 | 현재까지 방문한 노드의 방문 정보 |
즉, 현재 경우에서는 다음과 같은 경우가 존재한다.
1. 방문한적 없는 자식 노드가 있는 경우 (for문을 돌다가 visit이 0인 경우)
자식 노드에 방문 처리를 해준다.
양과 늑대의 수를 갱신해준다.
다시 0번 노드로 돌아간다.
덱에 넣어준다.
2. 자식 노드 모두 방문한 경우 (0번 노드로 되돌아가므로, 가능하다)
현재 양과 늑대의 수와 방문 정보를 유지한 채, 자식 노드로 이동해준다.
문제 처리
입력의 전처리
각 노드에 대해 방문 정보를 만들고 0으로 초기화한다.
0번 째 노드는 방문 처리 해준다.
각각의 부모마다 자식의 정보를 가지는 리스트 그래프를 만든다.
(리스트의 인덱스 = 부모 노드, 리스트 내용 = 자식 노드)
앞서 말했던 덱의 초기화 (시작 노드인 0번 노드의 초기화를 해준다.)
DFS 실행 및 정답 추출
DFS 시작 및 현재 정보 추출
현재 늑대가 양보다 같거나 많으면 종료
양의 최댓값 갱신
for문 시작
자식 노드를 하나씩 돌면서
자식 노드가 없는 경우는 패스
자식 노드를 처음 방문한 경우, 방문 정보와, 양,늑대 개수를 초기화 하여 0번 노드로 돌아간다.
자식 노드 모두 방문한 경우 계속 그래프를 타고 내려간다.
문제 후기
새로운 유형의 DFS 문제를 만난 것 같다.
다른 사람들의 풀이와 카카오의 해설을 보았는데, 내가 푼 방식과 다른 방식이었다.
0번째 노드를 다시 방문하지 않아도 되는 풀이 방법이었는데, 나에게는 아직 어려운 것 같았다.
다행이도 입력 정보가 길지 않아서 다행이기도 했지만,
내가 푼 방법도 정답 처리가 된 걸 보니, 3단계 문제가 맞는 것 같다고 생각했다.
물론 완벽한 정답은 아니어도, 문제를 맞춰 다행이다.
'알고리즘 > 프로그래머스 문제풀이' 카테고리의 다른 글
| [프로그래머스] 다단계 칫솔 판매 [Level 3] (python 파이썬) (0) | 2024.05.07 |
|---|---|
| [프로그래머스] 베스트앨범[Level 3] (python 파이썬) (0) | 2024.04.25 |
| [프로그래머스] 여행경로 [Level 3] (python 파이썬) [BFS] (0) | 2024.04.21 |
| [프로그래머스] 단어 변환 [Level 3] (python 파이썬) [DFS/BFS] (0) | 2024.04.21 |
| [프로그래머스] 징검다리 건너기 [Level 3] (python 파이썬) (0) | 2023.02.12 |