티스토리 뷰
https://programmers.co.kr/learn/courses/30/lessons/92343
코딩테스트 연습 - 양과 늑대
[0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5
programmers.co.kr
만약 그냥 인접한 이동가능한 노드로 이동하도록 한다면 다른 곳을 방문해서 양의 숫자를 불린 후에 다시 오면 갈수 있는 지점도 방문이 안될수도 있다.
예를들어 트리가 아래와 같을때 그냥 인접 노드를 방문하고 더이상 방문하지 않도록 한다면
0번 - 1번을 갔을때 양1늑대1 이므로 이동하지 않고 2-5-6-9-10 으로 이동해서 최대 양의 수가 4가 되버린다.
문재의 핵심은 한번 방문한 노드는 자유롭게 다시 이동할수 있다는 점이였다.
만약 0 - 2로 이동했다면 지금까지 방문한 노드 0번 2번 노드는 자유롭게 다시 돌아갈수 있으므로 바로 1번 노드로도 이동할수 있다는 것을 알 수 있다.
따라서 0-2로 이동했을때 다음에 내가 이동할수 있는 노드들은 1,5,6이다.
2에서 5로 이동했다면 다음에 내가 이동할수 있는 노드들은 1,6이다.
이런식으로 내가 다음으로 이동할수 있는 노드들을 기록해놓고 이동하면서 양과 늑대의 수를 세주고 노드를 이동했을때 늑대의 수가 양의 수와 같아진다면 리턴하도록 하면된다.
방문한 모든 지점을 벡터에 저장해놓는 방식
'PS' 카테고리의 다른 글
| 프로그래머스. 신고 결과 받기 (0) | 2022.02.02 |
|---|---|
| 프로그래머스. 파괴 되지 않은 건물 (0) | 2022.02.01 |
| 프로그래머스. 멀리 뛰기 (0) | 2022.01.31 |
| 프로그래머스. N-Queen (0) | 2022.01.30 |
| 백준 1614. 영식이의 손가락 (0) | 2022.01.30 |
- Total
- Today
- Yesterday
- Kruskal
- binary search
- DP
- permutation
- 조합
- Tree
- BFS
- 자료구조
- Spring
- Brute Force
- db
- C++
- Implementation
- C
- dfs
- Dijkstra
- Stack
- Python
- graph
- two pointer
- Unity
- back tracking
- greedy
- 재귀
- recursion
- priority queue
- 이분탐색
- floyd warshall
- CSS
- MVC
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 |