코테스터디

99클럽 코테 스터디 8일차 TIL | 단지번호붙이기 BFS풀이

2025.01.22

문제BOJ 2667번 : 단지번호붙이기 문제풀이시간복잡도N의 크기가 25 이하완탐으로 풀어도 무방하다. 구현 아이디어(DFS로 풀어도 무방하지만 이미 DFS로 풀어봤던 문제라 BFS로 풀었다.)입력숫자가 붙어있으므로 char로 입력받고 -'0'을 해준다.설계1. 보드입력이 완성된 상태에서 2중 for문으로 방문검사 및 보드검사를 한다.2. bfs에서 4방향 탐색을 통해 방문처리 및 단지 아파트 개수를 카운트한다.3. bfs 함수에서 카운트한 아파트 개수를 리턴한다.4. 리턴 받은 값을 백터에 저장한다.5. 백터를 오름차순으로 정렬하고 백터의 사이즈가 단지개수 이므로 출력하고 아파트 개수를 출력한다. 코드#include#include#include#includeusing namespace std;#defi..

알고리즘/코테스터디

99클럽 코테 스터디 7일차 TIL | 1차원 BFS와 노드,간선 문제

2025.01.21

문제BOJ 1697번 : 숨바꼭질https://www.acmicpc.net/problem/1697 BOJ 2606번 : 바이러스https://www.acmicpc.net/problem/2606숨바꼭질 문제풀이시간복잡도N이 100,000이라고 하여 O(NlgN) 이하로 풀어야 한다.일차원 배열 구조라서 BFS를 돌려도 O(N)에 풀 수 있다고 생각하였다. 구현 아이디어뒤로 한 칸 or 앞으로 한 칸 or 2배 순간이동처음 수빈이의 위치에서 시작하여 수빈이가 갈 수 있는 곳을 BFS를 돌리면 끝난다.처음 시작이 5라면 큐에 4, 6, 10을 넣고 기존 노드의 값에서 +1을 해준다. 그러면 4, 6, 10에는 2가 들어가고 4에서 뒤로, 앞으로, 순간이동을 또 큐에 넣게 되면 자동으로 동생으로까지의 최단경로..

99클럽 코테 스터디 8일차 TIL | 단지번호붙이기 BFS풀이

99클럽 코테 스터디 7일차 TIL | 1차원 BFS와 노드,간선 문제

티스토리툴바