BFS16 [ 자바스크립트(JavaScript) ] section09 - 6 - 섬나라아일랜드(DFS, BFS) 📍 section09 - 6 - 섬나라 아일랜드(BFS, DFS) 문제: N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 이 문제는 DFS 와 BFS탐색으로 모두 풀 수 있는 문제다. 이 방법을 이용하면 백준4963 - 섬의 개수도 한번 풀어보자! 먼저, DFS로 푸는 방법을 알아보자. visited 배열을 선언하지 않고 현재 좌표를 0으로 만든 다음에 대각선 좌표의 값이 1인 곳만 탐색한다.(이때, 재귀적으로 dfs 함수를 호출한다.) board를 돌면서 현재 좌표와 대각선 좌표까지 0이면 더 이상 탐색할 수 없으므로 다음 좌표로 넘어간다... 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 📍 section09 - 5 - 송아지 찾기(BFS: 상태트리탐색) 문제: 현수의 위치와 송아지의 위치가 수직선 상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. BFS를 사용하는 문제인데, 왜 BFS를 사용하는지 강의를 통해 배울 수 있었다. 결론적으로 상태 트리, 레벨 트리를 살펴보면서 깊이 우선 탐색인 DFS처럼 한 level만 끝까지 파고들며 target과 동일할 때까지 탐색하는 것이 아니라, 한 레벨에서 이동할 수 있는 좌표를 살펴보고 targ.. 2021. 10. 12. [ 자바스크립트(JavaScript) ] section09 - 4 - 이진트리 넓이우선탐색(BFS) 📍 section09 - 4 - 이진트리 넓이우선탐색(BFS) 다음과 같이 생긴 이진트리에서 BFS로 1 2 3 4 5 6 7 출력이 나와야 한다. visited 방문 배열을 선언할 필요 없이 nv>7 일 때는 더 이상 queue에 push 하지 않아도 되므로 break한다. queue에 더 이상 값이 없을 때까지 shift()한다. console.log(solution()); function solution(){ let queue = []; let answer = ""; queue.push(1); while (queue.length){ let v = queue.shift(); answer+=v+" "; for (let nv of [v*2, v*2+1]){ if (nv > 7) break; queue.p.. 2021. 10. 7. [ 파이썬(python) ] 백준 4179 - 불! (BFS) 📌 백준 4179 - 불! 문제 설명 💡 나의 풀이 나에겐 끔찍한 문제였다.. 이 문제에 오전, 오후를 완전히 쏟아버렸다. 😇 😇 수 없이 코드를 제출했다. 하지만, 돌아오는 대답은 인덱스 에러 혹은 틀렸습니다. 채점 중간에 71%에서 자꾸 오답 판정을 받았다. 틀린 이유를 단계별로 작성하면 인덱스 에러(Index Error): 변수 정의 단계에서 행과 열을 반대로 입력했다. 잘못된 변수 입력: 네이밍을 비슷하게 해서 그런지 중간에 다른 변수를 작성해서 제출했다. 잘못된 코드: 여기서 시간이 제일많이 걸렸는데 마지막 단계인 f_visited > j_visited 조건을 잘못 추가했다. 처음에는 f_visited[nx][ny] > j_visited[nx][ny]로 생각했는데 아니었다. 왜 그런가 하면 우리.. 2021. 4. 22. [ 파이썬(python) ] 백준 1743 - 음식물피하기 (BFS) 📌 백준 1743 - 음식물 피하기 문제 설명 💡 나의 풀이 전형적인 BFS 혹은 DFS 문제이고, 입력에 음식물의 좌표를 입력받아 BFS, DFS를 돌려 단순 개수를 파악하고 기존 개수와 현재 개수를 비교하여 더 큰 값으로 갱신해주면 되는 방향으로 문제를 풀면 된다. 여기서 약간 까다로운 부분은 좌표를 직접 입력받는 부분일 텐데, 우리가 사용하는 graph는 0부터 시작하므로 입력을 받을 때 -1처리를 해주면 오류없이 그래프에 입력할 수 있다. 풀이 흐름을 직접 그려봤다. import sys from collections import deque input = sys.stdin.readline def bfs(x, y): cnt = 0 queue = deque() queue.append((x, y)) vi.. 2021. 4. 22. 이전 1 2 3 4 다음
