본문 바로가기
728x90

BFS50

[python] 백준 11060 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 해결 판에 써져 있는 수 이하만큼 이동을 해서 최소한의 이동으로 끝까지 가는 문제 사실 bfs를 쓰고 이동을 1~판에 써져 있는 수 로 해서 바로 끝냈지만 메모리가 초과 되었다.(아무래도 MAX 이동 가능 거리가 100이기 때문에 많은 경우의 수가 deque로 들어가는 경우가 있기 때문) 그래서 어떻게 조건을 주어서 que에 들어가는 양을 줄일까 생각을 했는데 DP였다. DP로 이.. 2023. 4. 13.
[python] 백준 17142 연구소 3 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제 해결 시물레이션 + BFS가 바로 생각나는 문제 바이러스가 전염이 되는 것과 안되는 것이 처음에 존재하므로 존재하는 것을 고르는 경우의 수 combination을 사용한다. 각각의 경우 BFS를 사용하여 벽인 부분을 빼고 계속 전염시킨다. 만약 비전염 바이러스를 만나면 비전염바이러스가 전염이 되는 것과 같다. 모두 전염이 될 때의 시간을 결과값으로 받아서 최소값을 구하면 된다. ※ ps) 전형적인 삼.. 2023. 4. 12.
[python] 백준 16234 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 인구 이동이 진행될 때마다 계속 반복해서 진행하므로 시뮬레이션을 생각할 수 있다. 인구 이동 지역을 저장해야하므로 bfs를 이용해서 인구 이동 지역을 저장한후 평균을 그 지역 값에 넣어서 인구이동을 시킬 수 있다. 인구이동이 없으면 멈춰야한다. 이 부분에서 고민을 많이 했는데 이동한 지역이 없으면 인구 이동을 멈추는 변수 flag를 사용하여 인구 이동이 있으면 flag=1.. 2023. 4. 5.
[python] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 해결 사각형으로 영역을 막아놓고 나머지 빈 구역의 개수를 구하고 각 영역의 크기를 구하면 되는 문제 bfs를 이용해 영역을 메우면서 쉽게 풀 수 있다. CODE from collections import deque def bfs(x,y): global visited que = deque() que.append((x,y)) visited[y][x] = 1 cnt = 1 dx.. 2023. 4. 4.
728x90