본문 바로가기

BFS25

[백준-골드4] 2206번 벽 부수고 이동하기(BFS, 파이썬) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net - 우선 이 문제는 N,M이 최대 1000인 문제이다. 따라서 처음에는 모든 벽을 따로 리스트에 담고 벽을 하나씩 부쉇을때 모든 경로를 탐색하는 완전탐색으로 문제를 풀었을때는 시간초과가 났다. - 이 문제를 해결하기위해 visited 배열을 3차원 배열을 사용해서 해결했다. - 이 때 w가 1이면 아직 벽을 안부순 경우, 0이면 벽을 부순경우로 구분하였다. - 처음 bfs.. 2022. 2. 17.
[백준-골드4] 17142번 연구소 3(BFS, 파이썬) https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net [틀렸던 이유] - 활성화 바이러스 m개를 선택하면 비활성화 바이러스가 있다. bfs를 탐색하면서 이 부분을 고려하는게 어려웠다. - 비활성화 바이러스(2)는 지나갈수있다. 즉, 큐에 담을 수 있고, 이 때마다 거리가 증가 되어 오답을 유발한다. - 비활성화 바이러스가 마지막 경로(경계)에 있는 경우 거리가 정답보다 1크게 코드가 작동했었다. - 그래서 빈칸일때만 bfs를 동작시켰었는데 이래도 틀린다,,,.. 2022. 2. 13.
[백준-골드5] 7569번 토마토(BFS, 파이썬) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 우선 이 문제는 3차원 리스트의 BFS 문제이다. - 또한 최소 일수를 구하라고했으므로 이동 거리를 구해주면 됨 (최소 일수, 최소 이동 횟수 등 구하라했을 때 BFS의 거리를 구해주면 됨) - 우선 입력을 받으면서 문제 조건 중(처음부터 모든 토마토가 익어 있는 경우를 파악하기 위해 flag 변수를 이용 - 그리고 이동을 해야하는데 dz를 고려해야함 - 거리를 담을 리.. 2022. 2. 12.
[백준-골드3] 16236번 아기 상어(BFS, 구현, 파이썬) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net - 우선 처음으로 아기상어의 좌표를 찾는다.(시작 위치) - bfs함수를 이용해서 시작좌표를 기준으로 먹을 수 있는 물고기들을 eat 리스트에 담는다. - eat 리스트에는 거리, x좌표, y좌표를 담게된다. - bfs 탐색이 끝나면 eat 좌표를 거리, x,y 좌표 순서로 정렬한다.(문제 조건 충족시키기 위해) - eat이 비어있으면 더이상 먹을 물고기가 없는것이므로 리턴하고 eat에 원.. 2022. 2. 8.

티스토리툴바