728x90 반응형 너비우선탐색13 2022.05.17 [백준] (python 파이썬) 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 이 문제는 BFS를 사용하면 되는 문제이지만 물고기를 먹을 때마다 BFS를 해야 한다. 이유는 물고기를 먹을때마다 다음에 먹을 물고기의 최단거리를 구해야 하기 때문이다. 우선 shark_x,shark_y=0,0 # 상어의 위치 shark_size=2 # 상어의 크기 eat_cnt=0 # 상어가 먹은 물고기 수 fish_cnt=0 # 물고기 수 time=0 변수들을 선언해주었다. 이후 .. 2022. 5. 17. 2022.05.09 [백준] (python 파이썬) 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 이 문제를 해결하기 위해 BFS를 이용했다. 이유는 1을 루트 노드로 정했을 때, 1을 기준으로 각 자식노드로 내려가며 vis배열에 부모노드를 저장하기 위해서 이다. 우선 graph배열에 각 노드와 연결된 노드들을 저장했다. 그리고 각 노드에 대한 방문여부를 확인하고 각 노드의 부모 노드를 저장하기 위한 vis배열을 -1로 초기화하였다. 이 후, 루트 노드인 1을 bfs배열에 넣어 vis[1]을 0으로 선언 후 while문으로 각 노드의 자식노드를 확인했.. 2022. 5. 9. 2022.04.09 [백준] (파이썬 python) 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 이 문제는 bfs를 이용하여 문제를 해결하였다. 문제에서 주어지는 빙산의 배열을 arr에 담고 bfs를 돌려 각 빙산이 몇개의 바다에 접해 있는지 체크하여 빙산의 위치에 해당하는 melt배열에 접해있는 수를 저장해 주었다. 바로 arr배열에서 빙산이 녹은 값을 업데이트해주지 않은 이유는 만약 빙산이 녹아 바다(0)이 되었을 때, 다음의 빙산에 영향을 주기 때문에 bfs를 모두 돌고 난 .. 2022. 4. 9. 2022.03.29 [백준] (python 파이썬) 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 이 문제는 최단 거리를 구하는 bfs문제이다. 여기서 한가지를 더 생각해야 한다. 1,1에서 n,m까지 이동하면서 벽을 하나 부수고 이동할 수 있다. 그래서 벽을 부수지 않았을 때, 벽을 부수었을 때, 총 2가지 경우를 생각해 주어야 한다. 그래서 기존의 2차원배열에서 2가지 경우를 더한 3차원배열을 만들어 문제를 해결해야한다. 그래서 3차원 배열 visited을 만.. 2022. 3. 29. 이전 1 2 3 4 다음 728x90 반응형
