BFS

알고리즘 문제) BOJ 18188.다오의 데이트 링크 : https://www.acmicpc.net/problem/18188문제 요약N개의 명령이 주어진다각 명령은 움직일 수 있는 방향 2개가 주어진다다오가 명령에서 주어진 방향 중 하나를 선택해, 한칸씩 이동할 떄, 디지니를 만날 수 있는지를 찾아라블록과 경계밖으로는 이동할 수 없다시간 제한1초입력맵크기 세로H와 가로W가 주어진다H개의 줄에 맵 정보가 주어진다. : 빈칸D : 디오 위치Z : 디지니 위치@ : 블록명령 개수 N개가 주어진다각 명령마다 이동 가능한 방향 2개가 주어진다W : 위S : 아래A : 왼쪽D : 오른쪽출력만날 수 없다면 NO만날 수 있다면 YES를 출력하고, 어떻게 움직였는지 방향도 출력해라여러 방법이 있다면 아무거나 출력해도 된..

알고리즘 문제) BOJ 5944. Apple Delivery 링크 : https://www.acmicpc.net/problem/5944문제 요약C개의 길과 P개의 목초지가 존재이때, 각 길에는 거리비용이 존재PB에서 시작해 PA1와 PA2 목초지로 방문하려고 할 때, 이동해야할 최소 거리는?시간 제한2초입력C, P, PB, PA1, PA21 ≤ C ≤ 20만1 ≤ P ≤ 10만모든 거리의 합은 20억을 초과XC개의 줄에 두 목초지 번호와 그 사이 거리가 주어짐출력두 목초지를 방문할 때 이동할 최소 거리는?접근법PB에서 PA1과 PA2 방문을 위한 최소 경로를 구해야하므로 총 2가지 경로가 있을 수 있다PB → PA1 → PA2PB → PA2 → PA1따라서, PB ~ PA1 / PB ~ PA2 / PA1..

알고리즘 문제) BOJ 16197. 두 동전 링크 : https://www.acmicpc.net/problem/16197문제 요약N*N 보드와 4개의 버튼이 존재보드 위에는 동전이 하나씩 놓여져 있으며, 두 위치는 다르다버튼은 왼쪽, 오른쪽, 위, 아래 4가지가 존재이때, 버튼을 누르면 해당 방향으로 두 동전이 동시에 이동한다동전이 이동하려는 칸이벽 → 이동 X경계 밖 → 바깥으로 떨어짐그 외에는 해당 위치로 이동(이미 동전이 있는 경우에도 이동)두 동전 중 하나만 보드에서 떨어뜨리려면 최소 몇 번 클릭??시간 제한2초입력보드 세로 크기 N, 가로 크기 M1 ≤ N, M ≤ 20N개의 줄에 보드 상태가 주어짐o : 동전. : 빈칸# : 벽동전의 개수는 항상 2개출력두 동전 중 하나만 보드에서 떨어뜨리기 ..

알고리즘 문제) BOJ 16469. 소년 점프 링크 : https://www.acmicpc.net/problem/16469문제 요약마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다.뒤늦게 미로에 도착한 악당 무리 3명는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다.악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다.또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다.악당은 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신R*C 크기의 미로가 주어지고, 악당들의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 ..

알고리즘 문제) BOJ 1043. 거짓말 링크 : https://www.acmicpc.net/problem/1043문제 요약지연이는 거짓말하는 걸 좋아한다.파티에가서 거짓말을 하기 위해서는, 진실을 아는 사람이 있으면 안되고, 진실을 아는 사람과 같은 파티였던 사람이 있는 곳도 안된다.이때, 거짓말을 할 수 있는 파티 개수는?시간 제한2초입력사람 수 N, 파티 수 MN과 M은 50이하 자연수진실을 아는 사람 수와 사람의 번호가 주어짐사람의 번호는 1~N진실을 아는 사람 수는 0이상 50이하 정수M개의 줄에는 각 파티마다 오는 사람 수와 사람 번호가 차례로 주어진다.각 파티에 오는 사람 수는 1이상 50이하 정수출력거짓말을 할 수 있는 파티 개수접근법UNION & FIND로 풀었다,같은 파티에 참석한 경우..

알고리즘 문제) BOJ 4179. 불! 링크 : https://www.acmicpc.net/problem/4179문제 요약지훈이가 불에서 타기 전에 얼마나 빨리 탈출할 수 있는지 판단하기불은 매 분마다 한칸씩 수평, 수직으로 이동(네방향 확산)지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다지훈이와 불은 벽을 통과할 수 없다시간 제한1초입력R C1 ≤ R,C ≤ 1000행, 열R개의 줄에 맵이 주어짐‘#’ : 벽‘.’ : 빈칸‘J’ : 지훈이 초기 위치‘F’ : 블이 난 공간J는 입력에서 하나만 주어진다.출력지훈이가 미로를 탈출 할 수 없다면 IMPOSSIBLE가능하다면, 가장 빠른 탈출 시간 출력접근법bfs 알고리즘 사용우선 지훈이가 이동 가능한 경우는 여러 케이스가 있다큐에 bfs를 돌며 이동..

알고리즘 문제) BOJ 5913. 준규와 사과 링크 : https://www.acmicpc.net/problem/5913문제 요약5*5 크기의 과수원이 존재하며, 가장 왼쪾 위 칸은 (1,1), 가장 오른쪽 아래 칸은 (5,5)이다.이때 구역 k개를 제외한 구역에 사과 나무가 하나씩 존재한다준규는 (1,1)에서 사과를 수확, 해빈이는 (5,)에서 수확을 시작이때, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다.준규와 해빈이는 모든 사과를 수확하고 마지막에 같은 칸에서 만나려고 한다.이때, 사과를 수확하는 방법의 수를 구해라수학을 마친 칸으로는 다시 이동하지 않는다.또, 마지막을 제외하고 같은 칸에서 만날 수 없다.시간 제한1초입력k ( 0 ≤ k ≤ 22, 짝수)k개줄에는 사과 나무가 없는 칸의 위치가..

알고리즘 문제) BOJ 17182. 우주 탐사선 링크 : https://www.acmicpc.net/problem/17182문제 요약다음의 내용이 2차원 행렬로 주어짐ana호가 발사되는 행성 위치ana호가 행성 간 이동 하는데 걸리는 시간행성 위치는 0부터 시작 → 행렬에서 0번째 인덱스에 해당함을 의2차원 행렬에서 i, j번 요소는i번째 행성에서 j번째 행성에 도달하는데 걸리는 시간 의미i == j 일 때는 항상 0모든 행성을 탐사하는데 걸리는 최소 시간은?탐사 후 다시 시작 행성으로 돌아올 필요 없으며, 이미 방문한 행성 또 방문 가능시간 제한1초입력행성의 개수 N과 ana호가 발사되는 행성의 위치 K2 ≤ N ≤ 100 ≤ K N개 줄에 각 행성 간 이동 시간 Tij가 N개씩 띄어쓰기로 주어짐0 ≤..

알고리즘 문제) BOJ 14890. 경사로 링크 : https://www.acmicpc.net/problem/14890문제 요약N*N 지도가 존재길은 한 행, 한 열 전부를 의미한쪽 끝에서 다른쪽 끝까지 지나가는 것길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같을 것또는 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다경사로 높이는 항상 1, 길이는 L개수는 무한 개경사로 설치는 다음 조건을 만족할 것낮은 칸에 놓을 것경사로를 놓을 낮은 칸의 높이는 모두 같고, L개의 칸이 연속될 것낮은 칸과 높은 칸의 차이는 1일 것지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성시간 제한2초입력첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)둘째 줄부터 N개의 ..

알고리즘 문제) BOJ 2350. 대운하 링크 : https://www.acmicpc.net/problem/2350문제 요약N개의 도시 존재, M개의 운하 건설K개의 노선 준비각 노선의 도시 i와 j간을 운행하는 배는 도시 i와 j간 경로에 포함된 운하를 통과할 수 있어야 함배는 배의 크기 이상 폭의 운하만 통과가 가능하다K개의 줄에 각 노선을 운행할 수 있는 최대 배의 폭을 출력시간 제한1초입력도시의 수 N, 운하의 수 M, 노선의 수 KN ≤ 1000,M ≤ 100000,K ≤ 10000M개의 줄에는 세 정수 i, j, w도시 i와 j 사이에 폭이 w인 운하를 건설할 것임을 의미1 ≤ i, j ≤ N, w ≤ 200K개의 줄에는 각 노선이 연결하는 도시 i, j1 ≤ i, j ≤N출력K개의 줄에 각 ..