본문 바로가기
728x90

BFS50

[python] 백준 2636 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 해결 시간에 따라 치즈가 녹아서 없어지는 문제 → 시뮬레이션 가장자리는 치즈가 놓이지 않는다는 가정이 있으므로 그 중 하나인 (0,0)은 치즈가 없다. 치즈 안에 닫혀있는 공기는 상관x 따라서 치즈 밖에 있는 공기로 계속 퍼져나가고 치즈를 만나면 치즈를 녹인다.(그리고 더이상 그 지역에선 이동하지 않는다.) -> 이는 BFS를 통해 구현할 수 있다. 한 타임에 녹는 치즈의 개수를 세서 리스트에 저장한다. COD.. 2023. 4. 4.
[python] 백준 9205 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 해결 집(home)에서 목적지(end) 까지 도달 할 수 있는지 문제 중간 편의점(conv)은 지나도 되고 안지나도 된다. 50갈 때 마다 맥주 하나씩 없어지므로 목적지(end)까지 거리가 1000이하가 되는지 현재 위치에서 거리가 1000이하인 편의점을 하나씩 가보면서 확인 편의점을 하나씩 가보는 것은 bfs로 이동하는 것이 편하다. 만약 편의점을 다 돌면서 목적지(end)까지 거리가.. 2023. 3. 26.
[python] 백준 2573 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해결 빙산의 녹는 것을 계산한 다음 바다로 인해 하나였던 빙산이 두 개 이상으로 분리되는데 걸린 시간을 구하는 문제 bfs를 통해 빙산의 개수를 구할 수 있다. CODE import sys input = sys.stdin.readline from collections import deque def bfs(x,y): que = deque() que.append((x,y)) visited[.. 2023. 3. 26.
[python] 백준 15683 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해결 문제가 많이 어려웠다.(다른 분들의 풀이를 참고했다.) 결국 cctv 종류당 이동할 수 있는 방법의 수가 정해져 있기 때문에 dfs, bfs를 이용한 완전탐색을 해야한다. 이 사실을 알고 cctv당 이동 할 수 있는 방법을 리스트 안에 구현을 하면 사실 끝이다. 완전 탐색 후 가장 적게 사각지대가 생긴 개수를 구하면 된다. CODE import sys input = sys.s.. 2023. 3. 19.
728x90