너비 우선 탐색(Breadth First Search)
breadth: 폭, 너비(=width)(->length)
그래프 전체를 탐색하는 방법 중 깊이 있게 먼저 탐색하는 DFS와 달리 깊이가 같은 너비를 먼저 탐색하는 BFS
- BFS의 정의
- BFS의 특징
- BFS와 DFS 과정 비교
- BFS 구현
- BFS 문제 풀이
BFS의 개념
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
시작 정점으로 부터 가까운 정점(height가 낮은 곳부터)을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회함으로써 노드를 넓게(wide) 탐색한다.
BFS는 두 노드 사이의 최소 경로를 구하는 성질이 있어, 주로 '최단 경로', '최소 몇 번', '최소 이동 횟수', '최소 연산 횟수' 등과 같은 표현이 있는 문제에 주로 사용된다.
BFS의 특징
단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.
답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다.
최단경로가 존재한다면 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있다.
다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요하다.
방문한 노드를 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(Queue, 선입선출, FIFO)를 사용한다.
BFS와 DFS의 과정 비교
BFS,DFS의 목적 : 한 정점에서 시작해 연결된 모든 정점을 방문하는 것
BFS
Queue 인접점 우선
모든 인접 노드를 탐색하는 그래프 순회 알고리즘
가장 가까운 노드를 선택하고 탐색되지 않은 모든 노드를 탐색
모든 노드의 모든 이웃을 탐색하고 각 노드가 정확히 한 번 방문되고 노드가 두 번 방문하지 않음
알고리즘은 목표를 찾을 때까지 가장 가까운 각 노드에 대해 동일한 프로세스 따름
공간 복잡도 : O (V) (V :node의 수, E : edge의 수)
시간복잡도 : O (V + E) (V :node의 수, E : edge의 수)
방문순서 : A, B, C, D, G, H, I, E, F, J
DFS
Stack 순환호출
목표 노드 또는 하위 노드가 없는 노드를 찾을 때까지 더 깊고 깊게 진행
데드 엔드에서 아직 완전히 탐색되지 않은 최신 노드로 역 추적
프로세스는 BFS 알고리즘과 유사
방문하지 않은 노드로 이어지는 가장자리를 검색 가장자리라고 하며, 이미 방문한 노드로 이어지는 가장자리를 블록 가장자리라고 함
공간 복잡도 : O (V) (V :node의 수, E : edge의 수)
시간복잡도 : O (V + E) (V :node의 수, E : edge의 수)
방문순서 : A, B, D, E, F, C, G, H, I, J
BFS의 구현
//기본적인 bfs 구현
bfs() {
q.push(시작점);
while(q가 비워질때까지) {
now = q.front
q.pop;
for()
if(방문가능한 정점이라면)
q.push(next) // 다음정점
}
}
//정답을 찾고 종료하는 경우
bfs() {
q.push(시작점);
while(q가 비워질때까지) {
now = q.front
q.pop;
if(now == 정답) {
return //정답을 찾은 경우
}
for()
if(방문가능한 정점이라면)
q.push(next) // 다음정점
}
}
// 높이 측정
bfs() {
q.push(시작점);
while(q가 비워질때까지) {
int qsize = q.size(); //현재 큐에 저장된 갯수(같은 높이의 정점들)
while(qsize--) {
now = q.front
q.pop;
for()
if(방문가능한 정점이라면)
q.push(next) // 다음정점
}
height++; //높이측정
}
}
// 각 노드마다 높이 저장
bfs() {
q.push(시작점);
dist[시작점] = 0;
while(q가 비워질때까지) {
now = q.front
q.pop;
for()
if(방문가능한 정점이라면)
q.push(next) // 다음정점
dist[next] = dist[now] + 1 //높이 저장, int dist[N]
}
}
// 방문 순서 저장
bfs() {
q.push(시작점);
while(q가 비워질때까지) {
now = q.front
q.pop;
for()
if(방문가능한 정점이라면)
q.push(next) // 다음정점
dist[next] = dist[now] + i; //경로 저장, string dist[N]
}
}
위 그래프에서 A : 0, B : 1, C : 2, ... , J : 9라고 정점을 표현하면 간선은 아래와 같이 배열을 이용하여 표현할 수 있다.
이 경우 A(0) pop, A(0)에서 방문 가능한 정점 B(1)와 C(2)를 queue에 push
B(1) pop, B(1)에 방문 가능한 정점D(3)을 queue에 push
C(2) pop, C(2)에 방문 가능한 정점G(6), H(7), I(8)을 queue에 push
...
J(9) pop, 방문 가능한 정점이 없어 continue
queue에 정점이 없어 종료
출력한 결과는 queue에 들어간 순서와 같다. (FIFO)
#include <iostream>
#include <queue>
using namespace std;
#define N 10 //정점의 갯수
#define START 0
bool G[N + 1][N + 1]; //간선 표현
bool visited[N + 1]; //방문 처리
void bfs(int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int now = q.front(); //현재 방문한 노드
q.pop();
cout << now << " "; //현재 노드 출력
for (int i = 0; i < N; ++i) {// 인접 정점 중에서 방문가능한 정점 push
if (G[now][i] == true && visited[i] == false) {
q.push(i);
visited[i] = true;
}
}
}
}
int main(void) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> G[i][j];
}
}
visited[START] = true;
bfs(START);
cout << '\n';
}
/*********************************************************
입력 :
0 1 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 1 1 1 0
0 1 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
출력 :
0 1 2 3 6 7 8 4 5 9
*********************************************************/
A에서 J까지 최단경로, 즉 A에서 J까지의 높이를 구하는 방법은 아래와 같다.
//그래프의 높이를 구별하여 탐색하는 방법
#include <iostream>
#include <queue>
using namespace std;
#define N 10
#define START 0
#define END 9 // 목표 정점
bool G[N+1][N + 1];
bool visited[N + 1];
int bfs(int start) {
queue<int> q;
q.push(start);
int ret = 0; // 높이 = 최단거리 저장
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
int now = q.front();
q.pop();
if (now == END) {
return ret; // 현재 노드가 목표 노드와 같다면 리턴
}
for (int i = 0; i < N; ++i) {
if (G[now][i] == true && visited[i] == false) {
q.push(i);
visited[i] = true;
}
}
}
ret++;
}
return -1; // 전부 탐색하였으나 없을 경우 리턴-1
}
int main(void) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> G[i][j];
}
}
visited[START] = true;
cout << bfs(START) << '\n';
}
/*********************************************************
입력 :
0 1 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 1 1 1 0
0 1 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
출력 :
3
*********************************************************/
//visited처리와 동시에 높이(최단거리)를 저장하는 방법
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
#define N 10
#define START 0
#define END 9
bool G[N + 1][N + 1];
int visited[N + 1]; //int 배열 선언
void bfs(int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == END) {
return;
}
for (int i = 0; i < N; ++i) {
if (G[now][i] == true && visited[i] == -1) {
q.push(i);
visited[i] = visited[now] + 1; // 다음 방문할 정점은 기존꺼에 +1
}
}
}
}
int main(void) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> G[i][j];
}
}
memset(visited, -1, sizeof(visited)); // 방문하지 않은 정점은 -1로 초기화
visited[START] = 0; // 시작 지점은 높이 0
bfs(START);
cout << visited[END] << '\n';
}
/*********************************************************
입력 :
0 1 1 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0
1 0 0 0 0 0 1 1 1 0
0 1 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0
출력 :
3
*********************************************************///visited처리와 동시에 높이((visited[i]).length()), 경로(visited[i])를 저장하는 방법
#include <iostream>
#include <queue>
#include <string>
using namespace std;
#define N 10
#define START 0
#define END 9
bool G[N + 1][N + 1];
string visited[N + 1];
void bfs(int start) {
queue<int> q;
q.push(start);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == END) {
return;
}
for (int i = 0; i < N; ++i) {
if (G[now][i] == true && (visited[i]).length()==0) {
q.push(i);
visited[i] = visited[now] + to_string(i);
// 경로 저장
}
}
}
}
int main(void) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> G[i][j];
}
}
visited[START] = "0"; //시작노드
bfs(START);
cout << visited[END] << '\n';
for (int i = 0; i < 10; ++i)
cout << visited[i] << endl;
}
BFS 문제 풀이
16928 뱀과 사다리 게임 : https://www.acmicpc.net/problem/16928
'최소 몇번' 이라는 표현에서 BFS문제임을 알 수 있다.
이동하는 방법 : 주사위에서 나온 수(6가지), 도착한 칸이 사다리 또는 뱀인 경우 또 다른 칸으로 이동.
구현의 효율성을 위해서 사다리 또는 뱀일경우 map에 이동할 곳을 저장한다.
visited처리를 통해서 재방문을 막는다 : 어차피 두 번째 방문은 최단거리가 아니기 때문에
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int un, dn, map[101]; //up number, down number
bool visited[101];
int bfs() {
queue<int> q;
visited[1] = true;
q.push(1);
int c = 0;
while (!q.empty()) {
int now;
int qsize = q.size();
while (qsize--) {
now = q.front(); q.pop();
if (now > 100) continue;
if (map[now] != 0) now = map[now];
if (now == 100) break;
for (int i = 1; i <= 6; ++i) {
if (visited[now + i] == true) continue;
visited[now + i] = true;
q.push(now + i);
}
}
if (now == 100) break;
c++;
}
return c;
}
int main(void) {
cin >> un >> dn;
for (int i = 0, x, y; i < un + dn; ++i) {
cin >> x >> y;
map[x] = y;
}
cout << bfs() << '\n';
}
16948 데스 나이트 : https://www.acmicpc.net/problem/16948
'최소 이동 횟수' 즉 bfs 문제
최악의 경우 모든 칸을 방문하는 경우 즉 : 200^2
모두 한번씩 계산
시간복잡도 (O^2), 충분히 시간 안에 풀 수 있다
미로 탈출에서 조금 변형된 문제
한 곳에서 움직이는 최단거리를 모두 저장 후 마지막에 출력
#include <iostream>
#include <queue>
#include <cstring>
#include <tuple>
using namespace std;
int n, h1, h2, w1, w2;
int dist[201][201];
int dh[6] = {-2, -2, 0, 0, 2, 2};
int dw[6] = {-1, 1, -2, 2, -1, 1};
queue<pair<int, int> > q;
void bfs() {
q.push(make_pair(h1, w1));
dist[h1][w1] = 0;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
if (y == h2 && x == w2) break;
for (int i = 0; i < 6; ++i) {
int ny, nx;
ny = y + dh[i];
nx = x + dw[i];
if (0 <= ny && ny < n && 0 <= nx && nx < n);
else continue;
if (dist[ny][nx] != -1) continue;
dist[ny][nx] = dist[y][x] + 1;
q.push(make_pair(ny, nx));
}
}
}
int main(void) {
cin >> n >> h1 >> w1 >> h2 >>w2;
memset(dist, -1, sizeof(dist));
bfs();
cout << dist[h2][w2];
}
9019 DSLR : https://www.acmicpc.net/problem/9019
A를 B로 바꾸는 최소 연산 횟수
DSLR 각 네 가지 연산을 사용.
정적, 경우의 수 10000개,
어떻게 만들었는지도 알아야하는 문제.
string 변수를 만들어서 만들어 나가는 과정을 저장.
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int conv(int num, int i) {
int ans=-1;
switch (i) {
case 0:
ans = num * 2;
ans %= 10000;
break;
case 1:
ans = num - 1;
if (ans == -1) ans = 9999;
break;
case 2:
ans = (num%1000)*10 + num/1000;
break;
case 3:
ans = (num/10) + (num%10)*1000;
}
if (num == ans) return -1;
return ans;
}
char dslr[4] = { 'D', 'S', 'L', 'R' };
int main(void) {
int t;
cin >> t;
while (t--) {
int num1, num2;
cin >> num1 >> num2;
queue<int> q;
string dist[10000];
//bfs
q.push(num1);
while (!q.empty()) {
int now = q.front(); q.pop();
//cout << now << ", " << dist[now] << endl;
if (now == num2)break;
for (int i = 0; i < 4; ++i) {
int next = conv(now, i);
if (next == -1 ) continue;
if (dist[next] == "") {
dist[next] = dist[now] + dslr[i];
q.push(next);
}
}
}
//
cout << dist[num2] << '\n';
}
}
14502 연구소 : https://www.acmicpc.net/problem/14502
벽을 세개 세워서 바이러스가 퍼질 수 없는 영역의 크기를 구하는 문제.
bfs는 최소를 구하는 성질을 이용.
모든 칸을 방문하는 시간 복잡도 : O(NM)
세 칸을 선택하는 시간 복잡도 : O((NM)^3)
전체 시간 복잡도 : O((NM)^4), N, M <=8, 2^24, 이기 때문에 시간 안에 풀 수 있는 문제.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <cstring>
using namespace std;
int h, w;
int maps[9][9], maps2[9][9];
int ans;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
void bfs(vector<int> v) {
for (int a : v) {
int y = a / w, x = a % w;
if(maps[y][x]==0) maps[y][x] = 1;
else return;
}
queue<pair<int, int> > q;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (maps[i][j] == 2) {
q.push(make_pair(i, j));
}
}
}
while (!q.empty()) {
int y, x;
tie(y, x) = q.front(); q.pop();
maps[y][x] = 2;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0 <= ny && ny < h && 0 <= nx && nx < w && maps[ny][nx]==0) {
q.push(make_pair(ny, nx));
}
}
}
int sum = 0;
for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) if (maps[i][j] == 0) sum++;
if (sum > ans) ans = sum;
}
void dfs(vector<int> v, int last) { // v : 조합이 저장될 벡터, last : 마지막으로 뽑힌 수
if (v.size() == 3) {
memcpy(maps, maps2, sizeof(maps));
bfs(v);
return;
}
for (int i = last +1; i < h*w; ++i) {
//auto it = find(v.begin(), v.end(), i);
//if (it != v.end()) continue;
v.push_back(i);
dfs(v, i);
v.pop_back();
}
}
int main(void) {
cin >> h >> w;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
}
}
memcpy(maps2, maps, sizeof(maps2));
vector<int> v;
dfs(v, -1);
cout << ans;
}
2206 벽 부수고 이동하기 : https://www.acmicpc.net/problem/2206
NxM의 행렬로 나타내는 지도에서 최단거리를 구하는 문제
단, 벽은 한 번 부수고 지나갈 수 있다. // 문제조건이 조금 까다로운 문제
보통은 정점의 정의를 생각할 필요가 없다.
보통은 칸 또는 수가 정점.
벽을 부수지 않고 온 칸, 벽을 한번 부수고 온 칸
다르므로 한 칸이 같지가 않다. 고로 나눠줘야 한다.
정점 : 행과열의 좌표 + 벽을 부순횟수
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
using namespace std;
int h, w;
int ans = 1000000;
int maps[1001][1001];
int dist[1001][1001][2]; // dist[y][x][go] : (y,x)까지의 최단거리를 저장, go는 0일경우 벽을 안부숨, go는 1일경우 벽은 한번 부숨
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
void bfs() {
queue<tuple<int, int, int> > q; //좌표와 벽을부순 횟수를 저장,
q.push({ 0, 0, 0 });
dist[0][0][0] = 0;
while (!q.empty()) {
int y, x, go;
tie(y, x, go) = q.front();
q.pop();
if (y == h - 1 && x == w - 1) {
if(ans > dist[y][x][go])
ans = dist[y][x][go] +1;
return;
}
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
int ngo = go;
if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; //다음 좌표가 범위를 초과할경우 컨티뉴
if (maps[ny][nx] == 0 && dist[ny][nx][ngo] == 0) { //다음좌표가 빈공간일경우
q.push({ ny, nx, ngo });
dist[ny][nx][ngo] = dist[y][x][ngo] + 1;
}
if (maps[ny][nx] == 1 && ngo == 0 && dist[ny][nx][1] == 0) { //다음좌표가 벽일경우
ngo++;
q.push({ ny, nx, ngo });
dist[ny][nx][ngo] = dist[y][x][0] + 1;
}
}
}
}
int main(void) {
cin >> h >> w;
for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
scanf("%1d", &maps[i][j]);
}
bfs();
if (ans == 1000000) ans = -1;
cout << ans<<endl;
}
14442 벽 부수고 이동하기2 : https://www.acmicpc.net/problem/14442
어려운 문제는 아니었지만 실수를 해서 오래 걸렸다..
틀린 코드
if (maps[ny][nx] == 1 && ngo < k && dist[ny][nx][ngo] == 0) { //다음좌표가 벽일경우
ngo++;
q.push({ ny, nx, ngo });
dist[ny][nx][ngo] = dist[y][x][go] + 1;
}
맞은 코드
if (maps[ny][nx] == 1 && ngo < k && dist[ny][nx][ngo+1] == 0) { //다음좌표가 벽일경우
ngo++;
q.push({ ny, nx, ngo });
dist[ny][nx][ngo] = dist[y][x][go] + 1;
}
문제점 : 꼭 필요하지 않은 변수를 생성하고 햇갈릴만한 표기를 함으로 실수
if (maps[ny][nx] == 1 && go < k && dist[ny][nx][go+1] == 0) { //다음좌표가 벽일경우
q.push({ ny, nx, go+1 });
dist[ny][nx][go+1] = dist[y][x][go] + 1;
}#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
using namespace std;
int h, w, k;
int ans = 1000000;
int maps[1001][1001];
int dist[1001][1001][11]; // dist[y][x][go] : (y,x)까지의 최단거리를 저장, go는 0일경우 벽을 안부숨, go는 1일경우 벽은 한번 부숨
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
void bfs() {
queue<tuple<int, int, int> > q; //좌표와 벽을부순 횟수를 저장,
q.push({ 0, 0, 0 });
dist[0][0][0] = 0;
while (!q.empty()) {
int y, x, go;
tie(y, x, go) = q.front();
q.pop();
//printf("cnt : %d, y : %d, x : %d, go : %d\n", dist[y][x][go], y, x, go);
if (y == h - 1 && x == w - 1) {
if (ans > dist[y][x][go])
ans = dist[y][x][go] + 1;
return;
}
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; //다음 좌표가 범위를 초과할경우 컨티뉴
//if (visited[ny][nx] == 1) continue;
if (maps[ny][nx] == 0 && dist[ny][nx][go] == 0) { //다음좌표가 빈공간일경우
q.push({ ny, nx, go });
dist[ny][nx][go] = dist[y][x][go] + 1;
}
if (maps[ny][nx] == 1 && go < k && dist[ny][nx][go+1] == 0) { //다음좌표가 벽일경우
q.push({ ny, nx, go+1 });
dist[ny][nx][go+1] = dist[y][x][go] + 1;
}
}
}
}
int main(void) {
cin >> h >> w >> k;
for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
scanf("%1d", &maps[i][j]);
}
bfs();
if (ans == 1000000) ans = -1;
cout << ans << endl;
}
16933 벽 부수고 이동하기3 : https://www.acmicpc.net/problem/16933
낮에만 벽을 부술 수 있다는 조건이 추가됨.
-> 낮과 밤에 대한 정보를 추가해줌
낮, 밤을 포함하여 비짓처리를 해주면 쉽게 풀 수 있다.
가만히 있는 게 가능하게 코딩.
벽을 부술 수 있고, 낮과 밤이 있다는 조건으로
일반 미로탐색 처럼 상태가 (y, x)가 아니라 (y, x, crash, night)이다.
#include <cstdio>
#include <queue>
using namespace std;
struct wall {
int x, y, w, d;
};
int n, m, k;
bool check[1000][1000][11];
char a[1001][1001];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int bfs() {
queue<wall> q;
q.push({0, 0, 0, 1});
check[0][0][0] = true;
bool day = true;
while (!q.empty()) {
int p = q.size();
while (p--) {
int x = q.front().x, y = q.front().y;
int w = q.front().w, d = q.front().d; q.pop();
if (x == n-1 && y == m-1) return d;
for (int i=0; i<4; i++) {
int nx = x+dx[i], ny = y+dy[i], nw = w+1, nd = d+1;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (a[nx][ny] == '1' && !check[nx][ny][nw] && w < k) {
if (day) {
q.push({nx, ny, nw, nd});
check[nx][ny][nw] = true;
} else {
q.push({x, y, w, nd});
}
}
if (a[nx][ny] == '0' && !check[nx][ny][w]) {
q.push({nx, ny, w, nd});
check[nx][ny][w] = true;
}
}
}
day = !day;
}
return -1;
}
int main() {
scanf("%d %d %d", &n, &m, &k);
for (int i=0; i<n; i++) scanf("%s", a[i]);
printf("%d\n", bfs());
return 0;
}
6087 레이저 통신 : https://www.acmicpc.net/problem/6087
풀이과정
1. bfs로 c1, c2를 연결하는 최소 루트를 만들었을 때, 꺾이는 부분도 최소가 되지 않을까?
= 조금만 생각해도 반례를 찾을 수 있음
2. 한 칸이 기준이 아니라, 꺽이는 포인트를 기준으로 잡자,
=이동조건은 상, 하, 좌, 우 꺾이기 또는 이전에 가던 방향으로 계속 이동
=q에는 현재 위치와 가던 방향 세 변수를 저장
3. 각 노드에 현재 위치(y, x)와 방향만을 저장하니 반례가 등장
#반례 : 큐에 세 변수를 push한뒤, visited 배열이 다른 방향에서 온 노드에 의해 다른 값으로 업데이트되면 문제가 발생
36 40
*...................................
.*..*....************************...
..*..*...*C.....................*...
......*..********************...*...
.............................*.*....
..************************..*...*...
.*.......................*.*...*...*
*..********************..*..**.*....
......................*.....*..*....
............*..........*.*.*....*...
*******************.*..**.*.....*...
..................*...*........*....
.**************...*...*.*******...*.
..............*...*...*.............
.*............*...*...*...*.........
.*.************...*...*..*.*........
**............*...*...*.*...*.......
..*...........*...*...**.....*......
...*..........*...*...*.*.....*.....
....*.........*...*...*..*..........
.....*........*...*...*...*.........
......*.......*.*.*...*....*.......*
.......*......*...*...*.....*.....*.
*************.*...*...*......*...*..
*.............*...*...*.......*.*...
*..*..*...*....*..**..*........*....
*..*.*.*.*.**.*...*...*.............
*..**...*....*....*...*.............
*..*..............*...*.............
*..*.**************...*.............
*..*..............*...*.............
**C*.............*....*.............
..*.............*.....*.............
...............*......*.............
......................*.............
......................*.............
***.***.*.*.*.***.***..*..*.*...***.
*...*.*.*.*.*.**..***..*..*.*...**..
*...*.*..*.*...**.*.*..*..*.*...*...
***.***..*.*..***.*..*.****.***.***.
=방법 1 : 현재 위치(y, x), 가던 방향, 꺾인 개수 네 변수를 저장하여 구성
반례가 나왔던 테스트 케이스
<방법1>
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;
int visited[101][101]; //방문 확인, 꺽인 갯수
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
int main(void) {
int h, w, ch, cw;
char maps[101][101];
queue<tuple<int, int> > q; // y, x
cin >> w >> h;
for (int i = 0, count = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
if (maps[i][j] == 'C') {
if (count == 0) {
count++;
maps[i][j] = '.';
q.push({ i, j});
visited[i][j] = 1;
}
else {
ch = i;
cw = j;
}
}
}
}
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int ny, nx;
ny = y + dy[i];
nx = x + dx[i];
while (1) {
if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) break;
if (maps[ny][nx] == '*') break;
if (visited[ny][nx] == 0) { //방향이 다를 경우
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny, nx});
}
ny += dy[i];
nx += dx[i];
}
}
}
cout << visited[ch][cw] - 2 << endl;
}=방법 2 : 한 정점에서 각 방향으로 벽을 만나기 전까지 모두 q에 push
방법 2의 경우 한 정점에서 인접해 있는 곳만을 넣는 것이 아니라 같은 방향에 있는 정점을 모두 q에 push 한다는 점에서 bfs 문제풀이에 전형적이지 않은 접근 방법인 것 같다.
//방법2
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;
int visited[101][101]; //방문 확인, 꺽인 갯수
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
int main(void) {
int h, w, ch, cw;
char maps[101][101];
queue<tuple<int, int> > q; // y, x
cin >> w >> h;
for (int i = 0, count = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
if (maps[i][j] == 'C') {
if (count == 0) {
count++;
maps[i][j] = '.';
q.push({ i, j});
visited[i][j] = 1;
}
else {
ch = i;
cw = j;
}
}
}
}
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int ny, nx;
ny = y + dy[i];
nx = x + dx[i];
while (1) { //각 방향으로 벽을 만나기 전까지 계속 push
if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) break;
if (maps[ny][nx] == '*') break;
if (visited[ny][nx] == 0) {
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny, nx});
}
ny += dy[i];
nx += dx[i];
}
}
}
cout << visited[ch][cw] - 2 << endl;
}
16236 아기상어 : https://www.acmicpc.net/problem/16236
먹을 수 있는 물고기가 1마리일 경우 : 이동
먹을 수 있는 물고기가 2마리일 경우 : 가장 가까운 물고기부터, 가장 가까운 물고기가 여러 개일 경우, 위, 왼쪽 순으로 이동한다.
먹을 수 있는 물고기가 더 이상 없는 경우 : HELP
문제 풀이
1. 먹을 수 있는 물고기 중에서 가장 가까운 물고기가 여러개 일 경우에 아래와 같이 이동 순서를 위와 왼쪽을 우선으로 찾아 문제를 풀어보려 했었다.
반례 : 거리 2까지는 문제가 없었으나, 거리 3부터 문제가 발생했다.
이동 순서만 우선권을 부여했을 경우 18번과 19번에서 규칙에 어긋나는 현상이 발생하였다.
(18번이 19번보다 아래에 있지만 우선 방문)
2. 거리가 같을 경우, 모두 찾아 저장한 후에 그중에서 고르는 방법으로 해결
#include <iostream>
#include <tuple>
#include <queue>
using namespace std;
int visited[101][101]; //방문 확인, 꺽인 갯수
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
int main(void) {
int h, w, ch, cw;
char maps[101][101];
queue<tuple<int, int> > q; // y, x
cin >> w >> h;
for (int i = 0, count = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
if (maps[i][j] == 'C') {
if (count == 0) {
count++;
maps[i][j] = '.';
q.push({ i, j});
visited[i][j] = 1;
}
else {
ch = i;
cw = j;
}
}
}
}
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int ny, nx;
ny = y + dy[i];
nx = x + dx[i];
while (1) { //각 방향으로 벽을 만나기 전까지 계속 push
if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) break;
if (maps[ny][nx] == '*') break;
if (visited[ny][nx] == 0) {
visited[ny][nx] = visited[y][x] + 1;
q.push({ ny, nx});
}
ny += dy[i];
nx += dx[i];
}
}
}
cout << visited[ch][cw] - 2 << endl;
}
16954 움직이는 미로 탈출 : https://www.acmicpc.net/problem/16954
벽이 움직이는 미로 탈출 문제
벽을 먼저 이동시킨 후, 캐릭터를 이동.
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int h = 8,w = 8;
char maps[9][9];
int dy[9] = { 0,-1,-1, 0, 1, 1, 1, 0,-1};
int dx[9] = { 0, 0, 1, 1, 1,0,-1,-1,-1};
bool visited[9][9][9];
int bfs() {
queue<tuple<int, int, int> > q;
q.push({ 7, 0, 0 });
visited[7][0][0] = true;
while (!q.empty()) {
int y, x, t;
tie(y, x, t) = q.front(); q.pop();
//cout << y << x << t<<endl;
if (t == 8) return 1;
if (y == 0 && x == w - 1) return 1;
for (int i = 0; i < 9; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
int nt = min(t + 1, 8);
if (0 <= ny && ny < h && 0 <= nx && nx < w);
else continue;
if (ny - t >= 0 && maps[ny - t][nx] == '#') continue;
if (ny - t-1 >= 0 && maps[ny - t-1][nx] == '#') continue;
if (visited[ny][nx][nt] == false) {
q.push({ ny, nx, nt });
visited[ny][nx][nt] = true;
}
}
}
return 0;
}
int main(void) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
}
}
cout << bfs();
}
16956 늑대와 양 : https://www.acmicpc.net/problem/16956
늑대와 양이 같은 범위에 있지 않게 울타리를 놓는 문제
최소를 구하는 문제가 아니라(최소를 구해야 할경우 Mincot, 네트워크 플로우 문제)
늑대와 양이 인접해 있지 않을 경우 빈칸을 울타리로 놓아도 된다.
->늑대와 양이 인접해 있는지 구하는 문제
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
#define endl '\n';
char maps[501][501];
int dy[4] = { 0, 0, -1, 1 };
int dx[4] = { -1, 1, 0, 0 };
int main(void) {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int h, w;
cin >> h >> w;
vector<tuple<int, int> > v;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> maps[i][j];
if (maps[i][j] == 'S') v.push_back({ i, j });
}
}
for (auto a : v) {
int y, x;
tie(y, x) = a;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (0 <= nx && nx < w && 0 <= ny && ny < h) {
if (maps[ny][nx] == 'W') {
cout << 0;
return 0;
}
}
}
}
cout << 1 << endl;
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (maps[i][j] == '.') cout << "D";
else cout << maps[i][j];
}
cout << endl;
}
}
5014 스타트링크 : https://www.acmicpc.net/problem/5014
백만 이 범위여서
bfs로 완전탐색
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
#define endl '\n'
int visited[1000001];
int main(void) {
for (int i = 1; i <= 1000000; ++i) visited[i] = -1;
int n, start, end, up, down;
cin >> n >> start >> end >> up >> down;
queue<int> q;
visited[start] = 0;
q.push(start);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == end) {
cout << visited[now] << endl;
return 0;
}
if (now + up <= n && visited[now+up]==-1) {
visited[now + up] = visited[now] + 1;
q.push(now + up);
}
if (now - down >= 1 && visited[now - down] == -1) {
visited[now - down] = visited[now] + 1;
q.push(now - down);
}
}
cout << "use the stairs"<<endl;
}'Algorithm > Intermediate' 카테고리의 다른 글
| 분할 정복법(Divide and Conquer)(이분 탐색, 퀵 소트, 퀵 셀렉트, 머지 소트(병합 정렬))(Binary Search, Quick Sort, Quick Select, Merge Sort) (2) | 2021.08.05 |
|---|---|
| 그리디 알고리즘(Greedy Algorithm) (0) | 2021.06.12 |
| 브루트포스[2] - 재귀 함수 (2) | 2021.04.16 |
| 브루트포스[3]:백트레킹(backtracking) (0) | 2021.04.16 |
| 비트마스크(BitMask) (1) | 2021.04.14 |
