BFS

문제https://www.acmicpc.net/problem/14502백준 문제집 - 0x0D강 - 시뮬레이션 알고리즘: 시뮬레이션, BFS풀이바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을..

문제https://www.acmicpc.net/problem/16985백준 문제집 - 0x0D강 - 시뮬레이션 알고리즘: 시뮬레이션, BFS, 백트래킹풀이미로를 이 세상 그 누구보다 사랑하는 준현이는 3차원 미로 탈출 대회를 개최하기로 했다.대회의 규칙은 아래와 같다.- 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.- 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.회전을 완료한 후 참가자는 판 5개를 쌓는다. - 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇..

문제https://www.acmicpc.net/problem/2573백준 문제집 - 0x09강 - BFS 알고리즘: BFS풀이한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다. 2636: 치즈와 비슷한 문제다.차이가 있다면 치즈 문제에선 치즈의 겉표면(바깥부분)만 녹았으나, 빙산 문제에선 바다와 닿는 부분은 모두 녹는범위에 해당된다. 빙산이 두 덩어리가 되거나, 모두 녹을때까지 while문으로 체크한다.각 턴마다 visited를 새로 생성하고, 아직 방문하지 않은 좌표일 경우 bfs(x, y)를 실행하여 덩..

문제https://www.acmicpc.net/problem/9328백준 문제집 - 0x09강 - BFS 알고리즘: BFS풀이상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이는 상하좌우로만 이동할 수 있다.상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.  바로 앞전의 문제 11967: 불켜기 문제와 비슷한 느낌이다.물론 불켜기는 각 방에서 켤 수 있는 스위치들을 명시해놓은 상태이기도 하고, 구하고자 하는 값이 '불을 켤 수 있는 방' 자체였기 때..

문제https://www.acmicpc.net/problem/11967백준 문제집 - 0x09강 - BFS 알고리즘: BFS풀이농부 존은 최근에 N × N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2 ≤ N ≤ 100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다.베시는 유일하게 불이 켜져있는 방인 (1, 1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다.베시가 불을 켤 수 있는 방의 최대 개수를 구..