Flood Fill
- 피자배달(어려움)
#include<iostream>// 피자배달
#include<vector>
#include<cstring>
using namespace std;
int map[4][6] = {
0,0,0,2,1,0,
9,9,0,0,9,0,
3,9,9,0,0,0,
4,0,2,0,3,4,
};
struct node {
int y; int x; int level;
};
int bfs(int starty, int startx, int targetN, intky, intkx)
{
node queue[1000] = { starty,startx,0 };
int head = 0;
int tail = 1;
int used[4][6] = { 0 };
used[starty][startx] = 1;
int direct[4][2] = { 0,1,0,-1,1,0,-1,0 };
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++)
{
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>3 || dx>5)continue;
if (map[dy][dx] == 9)continue;
if (used[dy][dx] == 1)continue;
used[dy][dx] = 1;
queue[tail++] = { dy,dx,now.level + 1 };
if (map[dy][dx] == targetN) {
*ky = dy;
*kx = dx;
return now.level + 1;
}
}
}
}
int main()
{
int starty = 0;
int startx = 0;
int ky, kx;
int targetN = 1;
int cnt = 0;
while (1)
{
int ret = bfs(starty, startx, targetN, &ky, &kx);
if (ret == -1)break;
cnt += ret;
starty = ky;
startx = kx;
targetN++;
if (targetN == 5)break;
}
cout << cnt;
return 0;
}- 벽 두개 부수고 최소거리로 연결하기
1. 벽 정리(sett) 후 이중for문 통해 두개 선택
2. 선택한 벽 0 초기화 후 경로 확인
3. 돌아올때 백업된 벽 복구해주기 memcpy
#include<iostream>// 벽 두개!
#include<vector>
#include<cstring>
using namespace std;
int map[4][6] = {
0,0,1,1,1,1,
0,0,1,0,0,1,
0,0,1,0,0,1,
0,1,1,1,1,0,
};
int backup[4][6];
struct node { int y; int x; int level; };
int direct[4][2] = { 1,0,-1,0,0,-1,0,1 };
vector<node>wall;
int Min = 21e8;
void sett()
{
for (int y = 0; y < 4; y++)
{
for (int x = 0; x < 5; x++)
{
if (map[y][x] == 1)
{
wall.push_back({ y,x,0 });
}
}
}
}
int bfs()
{
node queue[1000] = { 0,0,0 };
int head = 0;
int tail = 1;
int used[4][6] = { 0 };
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>3 || dx>5)continue;
if (map[dy][dx] == 1)continue;
if (used[dy][dx] == 1)continue;
used[dy][dx] = 1;
queue[tail++] = { dy,dx,now.level + 1 };
if (dy == 3 && dx == 5) {
return now.level + 1;
}
}
}
}
int main()
{
sett();
memcpy(backup, map, 4 * 4 * 6);
// 벽 선택
for (int a = 0; a < wall.size(); a++)
{
for (int b = a + 1; b < wall.size(); b++)
{
// 원상복구 해주고
memcpy(map,backup, 4 * 4 * 6);
map[wall[a].y][wall[a].x] = 0;
map[wall[b].y][wall[b].x] = 0;
int ret = bfs();
if (ret < Min)Min = ret;
}
}
cout << Min;
return 0;
}- 최소거리로 두 다리 잇기
#include<iostream>
using namespace std;
int map[5][6] = {
1,1,1,0,0,0,
0,1,0,0,0,0,
0,0,0,0,0,1,
0,0,0,0,0,1,
0,0,0,1,1,1,
};
struct node {
int y, x;
int level;
};
int used[5][6];
int head, tail;
int direct[4][2] = {
0,1,0,-1,-1,0,1,0
};
node queue[1000];
void bfs1()
{
head = 0;
tail = 1;
queue[0] = { 0,0,0 };
used[0][0] = 1;
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++)
{
int dy = direct[t][0]+now.y;
int dx = direct[t][1]+now.x;
if (dy < 0 || dx < 0 || dy>4 || dx>5)continue;
if (map[dy][dx] == 0)continue;
if (used[dy][dx] == 1)continue;
used[dy][dx] = 1;
queue[tail++] = { dy,dx,now.level};
}
}
}
int bfs2()
{
head = 0;
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++)
{
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>4 || dx>5)continue;
if (used[dy][dx] == 1)continue;
used[dy][dx] = 1;
queue[tail++] = { dy,dx,now.level + 1 };
if (map[dy][dx] == 1) {
return now.level + 1;
}
map[dy][dx] = map[now.y][now.x] + 1;
}
}
}
int main()
{
bfs1(); // 등록
int ret = bfs2(); // 다리2 찾기
cout << ret;
return 0;
}- 여자친구데리고 식당가기 (미로찾기?)
#include<iostream> // going out
#include<cstring>
using namespace std;
int map[3][7] = {
0,0,0,0,0,1,0,
0,0,1,1,0,0,1,
0,0,0,1,1,0,0,
};
int direct[4][2] = {
0,1,0,-1,1,0,-1,0
};
struct node {
int y, x;
int level;
};
int cnt;
int bfs(int starty, int startx, int endy, int endx)
{
node queue[100] = { starty,startx,0 };
int head = 0, tail = 1;
int used[3][7];
used[starty][startx] = 1;
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++)
{
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>2 || dx>6)continue; // 맵 범위
if (used[dy][dx] == 1)continue; // 중복방지
if (map[dy][dx] == 1)continue; // 벽
used[dy][dx] = 1;
queue[tail++] = { dy,dx,now.level + 1 };
if (dy == endy && dx == endx)
{
return now.level + 1;
}
}
}
}
int main()
{
cnt += bfs(0,0,2,6);
cnt += bfs(2,6,2,0);
cout << cnt;
return 0;
}- 섬의 갯수 구하기
#include<iostream> // 섬의 갯수 구하기
using namespace std;
int map[5][5] = {
1,0,0,1,0,
0,0,1,0,0,
0,0,0,0,0,
0,1,1,1,0,
1,0,1,0,0,
};
int direct[4][2] = {
0,1,0,-1,1,0,-1,0
};
struct node {
int y, x;
};
int cnt;
void bfs(int yy, int xx)
{
node queue[1000] = { yy,xx };
int head = 0;
int tail = 1;
while (head != tail)
{
node now = queue[head++];
for (int t = 0; t < 4; t++)
{
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>4 || dx>4)continue;
if (map[dy][dx] == 0)continue;
map[dy][dx] = 0;
queue[tail++] = { dy,dx };
}
}
}
int main()
{
for (int i = 0; i < 5; i++)
{
for (int j = 0; j < 5; j++)
{
if (map[i][j] == 1) {
cnt++;
bfs(i, j);
}
}
}
cout << cnt;
return 0;
}- 섬의 크기 구하기 (응용 - 여러개의 섬, 가장 큰 크기의 섬 찾기)
//섬의 시작지점부터 0으로 바꾸면서 확인
#include<iostream>
using namespace std;
int map[5][5] = {
0,0,1,0,0,
0,1,1,0,0,
1,1,1,1,0,
0,0,1,0,0,
0,0,1,0,0,
};
struct node {
int y;
int x;
int level;
}queue[100];
int head;
int tail=1;
int direct[4][2] = {
0,1,
0,-1,
1,0,
-1,0
};
int main() {
int flag = 1;
for (int y = 0; y < 5; y++) {
for (int x = 0; x < 5; x++) {
if (map[y][x] == 1) {
queue[0] = { y,x,1 };
flag = 1;
break;
}
}if (flag == 1)break;
}
int cnt = 0;
node now;
while (head != tail) {
now = queue[head++];
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>4 || dx>4) continue;
if (map[dy][dx] == 0)continue;
map[dy][dx] = 0;
cnt++;
queue[tail++] = { dy,dx,now.level + 1 };
}
}
cout << cnt;
}- 산에서 불이났을때 돌을피해서 퍼져나갈경우 전체까지 몇일 걸리는가
#include<iostream>
using namespace std;
int map[5][5] = {
0,0,0,0,0,
0,1,0,1,0,
0,-1,0,0,0,
0,0,1,-1,0,
0,0,0,0,0,
};
struct node {
int y;
int x;
int level;
}queue[100];
int head;
int tail;
int direct[4][2] = {
0,1,
0,-1,
1,0,
-1,0
};
int main() {
for (int y = 0; y < 5; y++) {
for (int x = 0; x < 5; x++) {
if (map[y][x] == 1)
queue[tail++] = { y,x,1 };
}
}
node now;
while (head != tail) {
now = queue[head++];
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy>4 || dx>4) continue;
if (map[dy][dx] != 0)continue;
map[dy][dx] = map[now.y][now.x] + 1;
queue[tail++] = { dy,dx,now.level + 1 };
}
}
cout << now.level;
}- 입력받은 위치로부터 상하좌우방향으로 바이러스가 퍼져나갈때 전체가 다 걸리는데 몇일이 걸리는가
#include<iostream>
using namespace std;
int map[4][5];
struct node {
int y;
int x;
int level;
}queue[100];
int head = 0;
int tail = 1;
int direct[4][2] = {
0,1,
0,-1,
1,0,
-1,0
};
int main() {
node now;
cin >> queue[0].y >> queue[0].x;
queue[0].level = 0;
map[queue[0].y][queue[0].x] = 1;
while (head != tail) {
now = queue[head++];
for (int i = 0; i < 4; i++) {
int dy = now.y + direct[i][0];
int dx = now.x + direct[i][1];
if (dy < 0 || dx < 0 || dy>3 || dx>4) continue;
if (map[dy][dx] != 0) continue;
map[dy][dx] = map[now.y][now.x] + 1;
queue[tail++] = { dy,dx,now.level + 1 };
}
}
cout << map[queue[tail - 1].y][queue[tail - 1].x];
//cout << queue[tail - 1].level + 1;
}- (2,2) 지역부터 꽃이 피기 시작하여 전체 배열에 다 필때까지 몇일이 걸리는가
#include<iostream>
using namespace std;
int map[4][4];
struct node {
int y;
int x;
int level;
}queue[100] = { 2,2,0 };
int head = 0;
int tail = 1;
int direct[4][2] = {
0,1, //우
0,-1, //좌
1,0, //아래
-1,0, //위
};
int main() {
map[2][2] = 1;
while (head != tail) {
node now = queue[head++];
for (int t = 0; t < 4; t++) {
int dy = now.y + direct[t][0];
int dx = now.x + direct[t][1];
if (dy < 0 || dx < 0 || dy>3 || dx>3) continue;
if (map[dy][dx] != 0)continue;
map[dy][dx] = map[now.y][now.x] + 1;
queue[tail++] = { dy,dx,now.level + 1 };
}
}
cout << queue[tail - 1].level + 1;
}'Algorithm > C++' 카테고리의 다른 글
| [21.09.02] Hash (0) | 2021.09.02 |
|---|---|
| [21.08.31] DFS 연습하기 (0) | 2021.08.31 |
| [21.08.27]Priority_queue / Heap Sort / Dijkstra알고리즘 (0) | 2021.08.27 |
| [20.08.26]binary search 이진탐색알고리즘 (0) | 2021.08.26 |
| [21.08.25] SORT/ UNION-FIND/ 크루스칼알고리즘 (0) | 2021.08.25 |