[21.09.01]BFS 연습하기

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;
}