문제 링크: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 알고리즘 BFS를 사용하여 최단거리를 찾을 때, 현재까지 몇 개의 벽을 부쉈는지를 체크하기 위해서 3차원 visited 배열을 다음과 같이 선언합니다. visited[N][M][K] : (N,M) 좌표를 K개의 벽을 부수고 방문했을 때의 최단 거리 BFS의 큐에는 (좌표, 현재까지 몇 개의 벽을 부쉈는지)에 대한 정보를 담고, 다음과 같은 조..

문제 링크: https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net BFS 알고리즘 큐에 다음 두 가지를 삽입하는 BFS를 구현하면 되는 문제입니다. 1. cur * 2 2. cur * 10 + 1 큐가 비워지기 전에 A == B가 되는 수를 찾으면 성공이고 큐가 비워졌을 때 A == B가 되는 수를 못 찾으면 실패입니다. 숫자 맨 뒤에 1을 추가하는 것은 2로 나누어 떨어지지 않기 때문에 숫자에 2를 곱한 것과 중복되지 않습니다. 따라서 방문 체크 배열을 만들 필요가 없습니다. 숫자는 최대 10^9이므로 2번 연산에서 10^9 * 10 + 1을 하면 int의 최대 크기를 넘..

문제 링크: https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net BFS, 시뮬레이션 0. 입력 온도, 온풍기, 조사하는 칸을 각각 2차원 배열로 표현했습니다. int temperature[21][21]; int heater[21][21]; int inspection[21][21]; (a, b)와 (c, d) 사이에 벽이 있다는 것을 표현하기 위해서 다음과 같이 4차원 배열을 만들었습니다. bool wall[21][21][21][21]; //wall..

문제 링크: https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS 알고리즘 이 문제는 통나무의 중심 좌표를 가지고 목적지까지 최단거리로 이동하는 BFS를 구현하면 됩니다. 통나무는 현재 자신이 있는 좌표에서 BFS로 다음 좌표로 이동할 때 아래 두 가지 동작을 합니다. 1. 현재 좌표에 있는 통나무의 방향을 유지한 채로 4방향으로 이동한다. 2. 현재 좌표에 있는 통나무를 회전한 상태로 다음 좌표로 이동한다. 통나무의 ..

문제 링크: https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 그래프 이론, BFS 알고리즘 상근이가 50미터를 가려면 맥주를 한 병 마셔야 합니다. 맥주는 최대 20개까지 가지고 있을 수 있고 편의점에 가면 빈 맥주가 있을 때 리필할 수 있습니다. 상근이가 50미터마다 맥주 한 병을 마신다고 생각하지 말고 다음과 같이 바꿔서 생각하면 문제를 쉽게 풀 수 있습니다. 상근이는 맥주를 한 번에 다 먹는다. 그러면 상근이는 현재 위치에서 (먹은 ..

문제 링크: https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net BFS 알고리즘 먼저 2차원 배열을 선언하고, 음식물이 있는 곳을 1로 표현하고 음식물이 없는 곳을 0으로 표현합니다. 그다음 (r,c)에 있는 음식물에 대해서 인접한 음식물의 크기를 구할 수 있는 BFS를 구현합니다. 크기를 구하는 방법은 기본적인 BFS 구현에서 큐에 탐색할 next 좌표를 넣을 때 크기를 1 증가시키는 코드만 추가하면 됩니..

문제 링크:https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net BFS, 완전탐색 각각의 육지에 대해서 BFS로 다른 육지까지 최단거리를 모두 구하고, 최단거리 중에서 최장거리를 찾으면 됩니다. 가로, 세로의 크기는 최대 50 이하입니다. 임의의 한 정점에서 다른 모든 정점까지 BFS로 최단 거리를 구하면 O(N*M)의 시간복잡도를 가지고, 최대 정점의 개수는 N*M이므로 전체 시간 복잡도는 O((N*M)^2)의 시간복잡도가 됩니다. 따라서 주어진 시간..

문제 링크: https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 시뮬레이션, 우선순위 큐, BFS, 최단거리 먼저 택시를 기준으로 BFS를 사용해서 최단거리를 갱신합니다. 이때 다음 좌표로 이동할 때 택시의 연료가 부족하면 이동하면 안 됩니다. 현재 연료로 다음 좌표로 이동할 수 있으면 해당 손님의 좌표를 다음과 같은 기준으로 우선순위 큐에 기록합니다. 1. 현재 위치에서 최단거리가 가장 짧은 승객을 고른다...