BFS 10

[백준] 17144 미세먼지 안녕! - 골드 4

[오늘의 문제]https://www.acmicpc.net/problem/17144[오늘의 학습 키워드]구현BFS1. 문제설명 문제를 요약하자면 미세먼지가 가득한 방에 공기청정기를 가동시켜 미세먼지를 최대 T초간 제거 후 방에 남아있는 미세먼지의 총 양을 출력하는 문제입니다. 미세먼지는 1초동안 동시에 확산을 시작하는데확산의 조건은 다음과 같습니다.미세먼지는 인접한 4방향으로 확산한다.인접한 방향에 공기청정기가 있거나, 벽이 있다면 확신이 일어나지 않는다.확산되는 양은 현재 위치 (i, j) // 5 의 양 만큼 확산된다.확산 후 현재 위치 (i, j) 에 남는 양은 확산된 미세먼지의 수 (i, j) // 5 x (확산된 미세먼지 수) 만큼 감소된다즉 i, j 는 (i, j) - (i, j) // 5 * ..

알고리즘 2025.06.22

[백준] 3197 백조의 호수 - 플레 5

[오늘의 문제]https://www.acmicpc.net/problem/3197[오늘의 학습 키워드]너비 우선 탐색구현1. 문제설명 두 마리의 백조가 호수에 살아갈 때 두 마리의 백조가 서로 만나려고 합니다. 그러나 호수를 덮고 있는 얼음이 두 백조가 만나는 것을 방해합니다. 호수가 차례로 녹을 때, 매일 물 공간과 접촉한 모든 빙판이 녹습니다. 며칠이 지나야 백조가 만날 수 있는지 계산하는 프로그램을 작성하시오[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ R, C ≤ 1500 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. 2. 접근방식문제만 보면 구현 방식 자체는 간단합니다. 백조의 위치를 구한 뒤 시..

알고리즘 2025.06.16

[백준] 9328 열쇠 - 골드

[오늘의 문제]https://www.acmicpc.net/problem/9328[오늘의 학습 키워드]BFS, 너비 우선 탐색그래프 이론, 그래프 탐색, 격자 그래프구현1. 문제설명 상근이가 빌딩을 탈출할 때 최대한 많은 비밀 문서를 가져오려고 합니다. 상근이는 빌딩의 외부에서 벽이 아닌 곳으로 출입하는데 이때 벽이 아니라는 의미는 빈 공간 혹은 문, 키 등을 의미합니다. 상근이는 문(대문자 영어)을 만났을 때 키(소문자 영어)가 있는 경우 해당 문을 열고 다음 위치로 이동합니다. 기존에 보유중인 키도 있고 빌딩에 흩어진 키를 주워서 문을 열어 이동할 수 도 있습니다. 상근이는 4방향으로만 이동이 가능할 때 최대한 많은 문서를 주울수 있는 경우를 찾아 출력하는 프로그램을 만들어야 합니다.[제한사항]시간 제..

알고리즘 2025.06.14

[백준]11967 불 켜기 - 골드 2

[오늘의 문제]https://www.acmicpc.net/problem/11967[오늘의 학습 키워드]그래프 이론그래프 탐색너비 우선 탐색, BFS구현1. 문제설명 암소 배시는 불이 켜진곳 으로만 이동이 가능합니다. 1, 1 위치에 다른 방의 불을 켜고 끌 수 있는 스위치가 있을 때 해당 방의 불을 켠 후 불이 켜진방으로 이동이 가능합니다. 이렇게 해서 배시가 이동이 가능한 방의 개수를 구하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 512MB2 ≤ N ≤ 1001 ≤ M ≤ 20,0002. 접근방식 배시가 이동 가능한 좌표의 크기는 N x N 이고 불이 켜진 정보가 M개의 줄에 걸쳐 주어집니다. 이때 불의 정보는 x1, y1 -> x2, y2의 불을 켤 수 있습니다. 이 구조는 딕셔너리의 구조..

알고리즘 2025.06.12

[백준] 16920 확장 게임 - 골드 2

[오늘의 문제]https://www.acmicpc.net/problem/16920[오늘의 학습 키워드]그래프 탐색그래프 이론너비 우선 탐색, BFS구현1. 문제설명 격자판 위에 플레이어의 번호와 동일한 성이 존재합니다. 각 플레이어 별로 움직일 수 있는 범위 S가 주어질 때, 1번 플레이어 부터 9번 플레이어 까지 순서대로 자신의 성을 확장합니다. 예를들어 1번 플레이어는 성이 0, 0 위치에 존재하고 2칸의 범위를 움직일 수 있습니다.2번 플레이어는 3, 3에 성이 존재하고 1칸의 범위를 움직일 수 있습니다. 1턴 움직이면 각 플레이어의 성이 이렇게 확장 됩니다. 다음턴에는 이렇게 확장되어 1번 플레이어가 총 13칸을 차지하고 2번 플레이어는 3칸을 차지하게 됩니다. 이렇게 동작하도록 코드를 작성..

알고리즘 2025.06.11

[백준] 9466 텀 프로젝트 - 골드

[오늘의 문제]https://www.acmicpc.net/problem/9466[오늘의 학습 키워드]DFS깊이 우선 탐색그래프 탐색그래프 이론구현1. 문제설명 학생들이 각자 원하는 팀이 있습니다. 위 그림에서 1번 학생은 3번 학생과 팀을 원하고 3번 학생은 혼자 팀을 하기 원합니다. 이 경우 3번 학생이 3번을 선택하였기 때문에 3번 학생혼자 프로젝트를 실시하고 1번 학생을 팀을 이루지 못했습니다. 2번의 경우 1번을 원하지만 1번은 이미 3번을 원했기에 2번도 팀을 이루지 못합니다. 3번의 경우 팀을 이뤘고 4번은 7번을 7번은 6번을 6번은 4번을 원하고 있습니다. 각각 원하는 사람이 겹치지 않고 6번이 4번을 선택했을 때 4번은 다시 7번을 선택하는 사이클이 완성되었으니 이 3명은 팀을 이뤘습니..

알고리즘 2025.06.10

[백준] 5427 불 - 골드 4

[오늘의 문제]https://www.acmicpc.net/problem/5427[오늘의 학습 키워드]너비 우선 탐색그래프 탐색, 그래프 이론구현격자 그래프1. 문제설명 상근이는 빌딩에서 탈출하려 합니다. 빌딩의 크기는 각각 N, M 으로 주어지며 상근이의 위치와, 불이 난 곳, 벽, 빈 공간의 정보가 2차원 배열에 담겨 주어집니다. 불이 매 초마다 4방향으로 번지기 시작할 때 상근이가 빌딩에서 탈출이 가능하다면 탈출에 걸린 시간을 탈출이 불가능하다면 IMPOSSIBLE을 반환하는 프로그램을 작성하는 문제 입니다.[제한사항]시간 제한 1초메모리 제한 256MB테스트 케이스는 최대 100개1 ≤ N, M ≤ 10002. 접근방식저는 우선 빌딩에 불을 모두 지르고 상근이가 탈출이 가능한지를 판별하였습니다. 불..

알고리즘 2025.06.09

[백준] 1600 말이 되고픈 원숭이 - 골드 3

[오늘의 문제]https://www.acmicpc.net/problem/1600[오늘의 학습 키워드]너비 우선 탐색구현그래프 탐색, 그래프 이론격자 그래프1. 문제설명 동물원을 탈출한 원숭이가 0, 0 좌표에 존재합니다. 이 원숭이가 N, M 좌표로 이동하려고 하는데 말이 되고 싶어 말처럼 이동이 가능합니다. 말처럼 이동하는데는 최대 K번 이동이 가능하고 그 이후에는 인접한 4방향으로 이동이 가능합니다. 격자판에 정보가 주어질 때, 원숭이가 최소한의 동작으로 0, 0 좌표에서 N, M 좌표로 이동하는 방법을 구하는 문제 입니다.[제한사항]시간 제한 2초메모리 제한 256MBN과 M은 1이상 200이하의 자연수K는 0이상 30이하의 정수격자판에 주어진 정보 0은 평지, 1은 장애물2. 접근방식이 문제를 해..

알고리즘 2025.06.07

[백준] 18405 경쟁적 전염 - 골드5

[오늘의 문제https://www.acmicpc.net/problem/18405[오늘의 학습 키워드]BFS, 구현1. 문제 설명 N x N 크기의 시험관이 주어집니다. 해당 시험관에는 K개의 바이러스가 존재하는데 바이러스는 순서대로 1번부터 K번까지 존재합니다. 바이러스는 낮은 번호부터 빈 칸에 전염을 시작하는데 만약 전염하려는 칸에 이미 바이러스가 존재하는 경우 해당 칸은 전염을 시킬 수 없습니다. 바이러스는 전염을 위해 상, 하, 좌, 우 4방향으로 동시에 전염을 시킬 수 있으며 주어진 S초가 경과하였을 때, 주어진 위치에 존재하는 바이러스 번호를 출력하는 프로그램을 작성해야 합니다.[제한사항]시간 제한 1초메모리 제한 256MB1 ≤ N ≤ 200, 1 ≤ K ≤ 1,0000 ≤ S ≤ 10,000..

알고리즘 2025.04.13

[백준] 2206 - 벽 부수고 이동하기 - 골드 3

[오늘의 문제]https://www.acmicpc.net/problem/2206[오늘의 학습 키워드]BFS1. 문제 설명 N x M 행렬의 미로를 탈출하는 문제입니다. 0은 이동이 가능한 길1은 이동이 불가능한 벽을 의미하는데 벽은 1번 부술수 있습니다. 모든 경로중 가장 짧은 경로를 찾아서 이동 시간을 출력하는 문제입니다.만약 탈출이 불가능한 경우 -1을 반환합니다.[제한 사항]시간 제한 2초메모리 제한 192MB1 ≤ N ≤ 1,0001 ≤ M ≤ 1,0002. 접근 방식 전형적인 BFS 문제 같습니다. 벽을 부술수 있을 때 이동 가능한 모든 경로를 queue에 넣어서 다음 위치를 탐색합니다. 그 중 벽을 부숴야 하면 부수고 이동한 뒤 그 상태를 queue에 넣어서 종료까지 탐색을 실시합니다. 한가지..

알고리즘 2025.04.09