백준/탐색4 백준 1981 c++ "배열에서 이동" -PlusUltraCode- https://www.acmicpc.net/problem/1981 [필자 사고]평범한 BFS탐색문제이지만 이분탐색이 들어가 색다른 느낌이 든다.미드값을 가지고 BFS 0부터 mid값부터 시작하여 i부터 mid값+ i 의 숫자들은 모두 false 형태로 바꾸고탐색을 진행하다 성공하면 end값을 더 줄이고 그렇지 않으면 start값을 늘리는 형식.. 이분탐색을 더욱 깊이 있게 배워나가는 시간이였다.[코드 해설] 입력 처리 (Input 함수)사용자로부터 NxN 크기의 2차원 배열(arr)과 그 값들을 입력받는다.배열의 각 값을 읽으면서 최대값(maxValue)과 최소값(minValue)을 갱신한다.BFS를 활용한 경로 검증 (BFS 함수)특정 diff 값을 기준으로 이동 가능한 경로가 존재하는지 확인한다.mi.. 2025. 1. 8. 백준 8111 c++ "0과 1" -PlusUltraCode- https://www.acmicpc.net/problem/8111 [필자 사고]탐색 문제이다. 이 문제에서 핵심 알고리즘은 부모추적 알고리즘과 모듈러 공식 및 BFS탐색 방법인거 같다.모듈로 공식으로 인해 방문 배열을 입력된 숫자의 나머지로 선정할수 있고,부모추적 인덱스 즉 DFS를 이용하여 부모추적을하여 map에서 원하는 글자를 꺼내어 출력을 하면 된다. 한 문제에서 3가지 알고리즘을 배워서 좋은 학습 문제였다. [코드 해설]위 코드를 설명하면 다음과 같습니다:BFS를 이용한 탐색 과정BFS 함수는 큐(myQueue)를 사용하여 모듈로 연산을 기반으로 숫자를 생성하고, 목표 상태(나머지가 0)가 될 수 있는지를 판단합니다.시작은 1 % num으로 하며, 이를 큐에 넣고 방문 표시(visited)를 합니.. 2025. 1. 8. 백준 3197 c++ "백조의 호수" -PlusUltraCode- https://www.acmicpc.net/problem/3197[필자 사고]BFS 탐색문제이다. 필자는 이 문제 전에는 queue를 하나만 써오던 습관이 있었는데ㅇㅣ 문제에서는 임시큐까지 총 4개의 큐를 사용해야 풀 수 있는 문제이다.고정관념을 깨게 해준 문재이다.주의할점은 먼저 오리가 탐색해야된다. 오리가 탐색한 지역은 방문처리를 하고 오리를 만날경우 끝내면 된다.다음으로 물이 X자를 만나면 X자를 '.'으로 교체후 임시큐에 저장한다.여기서 중요한건 물은 방문처리를 건들지 않는다는 것이다. [코드 해설]코드 설명입력 처리 및 초기화Input 함수는 격자 배열(arr)의 크기 N×MN \times MN×M과 내용을 입력받습니다.배열 내의 각 좌표를 확인하며, 시작점(L)과 물이 있는 좌표(.)를 찾아 .. 2025. 1. 8. 백준 17071 c++ "숨바꼭질 5" -PlusUltraCode- https://www.acmicpc.net/problem/17071 [필자 사고]이 문제는 BFS 탐색 알고리즘을 이용하여 풀 수 있다.필자는 이 문제에서 방문지역을 어떻게 체크할지 고민했는데 다른 분들의 자료들을 찾아보니visited[2][500001] 와 같은 형식으로 작성했따.시간을 홀수 시간과 짝수 시간으로 방문지역을 체크했는데 곰곰히 생각해보니 오른쪽 왼쪽 즉 왔다 갔다 할 수있다.왔다 갔다 는 총 2초가 걸리므로 이미 그 지역을 방문한 흔적이 있다면 true로 해놓고동생이 만약 그 지역에 방문하고 해당 시간이 홀수인지 짝수인지 맞다면 반복문을 끝내는 형식으로코드를 작성하면 된다.[코드 해설]1. BFS를 이용한 탐색이 코드는 BFS(Breadth-First Search)를 사용하여 문제를 해.. 2025. 1. 7. 이전 1 다음
