Ctstudy3
layout: single
title: “[BOJ]DFS&BFS 42제”
categories: boj
toc: true
toc_sticky: true
Coding Test Study 3
💻230320~230325 (실4~실3)
1. 반복수열 (실4) 2331
visited: [57, 74, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37, …]
두 번 방문한 수가 나오면 그 뒤는 계속 겹치기 때문에 그 수의 앞까지가 반복되지 않는 부분이다
ex) 37이 두 번 방문한 수 이므로 37의 인덱스 값이 반복되지 않는 배열의 길이가 된다
2. The Game of Death(실4) 11558
입력받는 거 주의 : T번의 케이스, 입력 후 바로 dfs 호출 후 결과값 출력
첫 번째 사람이 가리킨 사람부터 시작, cnt 1부터 시작
지목된 사람이 또 지목되면 반복이 생기면서 주경이가 안 걸림 -> 또 지목이 일어나면 0 출력 후 dfs 함수 종료
3. 바이러스(실3) 2606
1과 연결되어 있는 컴퓨터 수 출력 : dfs(1)한 후 개수 출력하면 끝
1번 컴퓨터는 개수에서 빼줘야 함
4. 촌수계산(실3) 2644
visited[v]를 해준 후 v==p2인지 확인(순서 중요) : 마지막에 visited[p2]가 0이면 -1를 출력해야하기 때문
5. 순열사이클 (실3) 10451
인덱스에서 값으로 향하는 그래프이기 때문에 arr가 곧 graph임 : graph 안 만들어도 됨
인덱스 주의 : 인덱스는 0부터 시작하지만 1노드이기 때문에 arr[v]-1로 불러야함
💻230325~230331 (실3~실2)
6. 늑대와 양(실3) 16956
주의: 1과 0만 맞으면 그래프는 상관없는 줄 알았는데 D가 있어야 하는 것 같음
.을 모두 D로 바꾸고 결괏값과 그래프를 출력하면 정답
7. 짝 정하기(실3) 2599
| [1] A남B여 | [2] A남C여 |
| [3] B남A여 | [4] B남C여 |
| [5] C남A여 | [6] C남B여 |
[1]과 [2]를 더하면 A남자의 수
[2]와 [4]를 더하면 C여자의 수
이런 식으로 [1]의 값이 변할 때 나머지 5개 값을 다 구할 수 있음
모든 값이 0 이상이면 짝이 성립하는 경우임
8. DFS와 BFS(실2) 1260
주의: 그래프 만든 후 각 배열 안의 값을 오름차순 정렬 해줘야 함(출력 예시 꼭 보기)
dfs와 bfs를 정석적으로 풀면서 출력하면 됨
9. 유기농배추 (실2) 1012
입력값과 예시 그림을 보면 [X][Y]가 아니라 [Y][X]로 입력되어야 함
1이면 0으로 바꿔주는게 dfs함수임
1일때는 dfs를 다 돌고 True를 반환, 0이면 바로 False를 반환함
dfs가 너무 깊어지면 RecursionError 발생 -> sys.setrecursionlimit(10000) 추가해 주기
10. 연결요소의 개수 (실2) 11724
dfs가 너무 깊어지면 RecursionError 발생 -> sys.setrecursionlimit(10000) 추가해 주거나 / BFS로 풀기
vistied 배열을 돌면서 아직 방문하지 않은 인덱스가 있으면 cnt 올려주고 bfs 호출
💻230624~230630 (실2~실2)
11. 외판원 순회2(실2) 10971
dfs를 돌고 나오면 visited를 초기화 해줌
0,0에서 시작하는 경우만 해도 순회이기 때문에 모든 경우를 다 돌 수 있음
12. 침투(실2) 13565
마지막 줄에서 하나라도 2 이상인게 있으면 침투를 했다는 뜻
13. 트리의 부모 찾기(실2) 11725
어떤 것의 부모가 없으면 그것의 부모는 v가 된다
💻230701~230707 (실2~실2)
14. 점프 점프(실2) 14248
밟은 돌을 visited=1로 바꾸고 1인 것의 개수 세기
15. 텔레포트 정거장(실2) 18232
자기 양 옆값과 텔레포트로 갈 수 있는 값을 넣어야함
16. 특정 거리의 도시 찾기(실2) 18352
단방향 그래프
17. 회의실 배정 2(실2) 19621
회의시간 빠른 순대로 입력한다는 말이 없기 때문에 정렬을 해줘야 함 → 안해주면 80퍼에서 틀림
💻230708~230715 (실2~골5)
18. 맹세(실2) 3407
19. 친구(실2) 1058
A와 A는 친구가 아니기 때문에 i==j일 때 continue
20. 양 한마리… 양 두마리…(실2) 11123
dfs는 visited를 갱신하는 용도이다.
조건에 맞다면 True를 반환한다. True일 때의 경우를 모두 세면 정답이다.
💻 2024~2025 (실2~골5)
21. 그대, 그머가 되어(실2) 14496
23. 미로탐색 (실1) 2178
"최소의 칸 수"를 구해야 하므로 BFS를 사용한다.
다음 위치는 "현재 위치+1"로 구한다.(19줄)
24. 1로 만들기 2(실1) 12852
25. 숨바꼭질 (실1) 1697
26. 단지번호 붙이기 (실1) 2667
그래프를 탐색하면서 1이면 dfs를 돌린다.
이때 dfs 함수의 역할은 집을 카운트하면서 0으로 바꾸는 역할이다.
27. 케빈베이컨의 6단계 법칙(실1) 1389
28. 안전영역(실1) 2468
29. 나이트의 이동 (실1) 7562
30. 영역 구하기(실1) 2583
31. 현수막(실1) 14716
32. 돌다리(실1) 12761
33. 효율적인 해킹(실1) 1325
bfs를 돌리면서 해킹할 수 있는 컴퓨터의 개수를 센다.
모든 개수를 result 배열에 저장한 후 result의 max값과 같은 컴퓨터를 모두 출력한다.
34. 음식물 피하기(실1) 1743
35. 양(실1) 3184
36. 양치기 꿍(실1) 3187
37. 그림(실1) 1926
38. 전쟁 - 전투(실1) 1303
39. 숫자놀이(실1) 1679
40. 십자 뒤집기(골5) 10472
41. 점프 게임(골5) 15558
(0, 0)부터 시작하여 y+1, y-1, y+k가 조건에 맞을 때 큐에 넣는다.
매 초마다 칸이 사라지므로 빨리 도착하는 게 중요하기 때문에 BFS를 사용했다.
42. 토마토 (골5) 7576
1인 것부터 BFS를 돌린다. 0이면 이전 값 +1로 바꾼다.
모든 토마토가 모두 익는 데까지 걸린 일수는 배열의 최댓값이다.
댓글남기기