https://www.acmicpc.net/problem/1600

1. 문제설명

일반적인 BFS문제는 상하좌우로 네칸만 움직인다.

이 문제는 원숭이가 평소에는 상하좌우로 네칸을 움직일 수 있다가

K번의 기회로 말처럼 더 넓은 범위를 움직일 수 있다.

이런 문제를 표현하기 위해서는 최대 K번 말처럼 움직일 수 있으므로

현재까지 원숭이가 총 몇 번 말처럼 움직였는지 상태를 저장해줄 필요가 있다.

그래서 이러한 문제 유형을 나는 상태 추가 BFS라고 부르기로 했다.

그냥 저 혼자 부르는 거니까 다른데 가서 유식한 척 말하시면 안됩니다.

2. 상태추가?

왜 상태추가라고 하냐면

보통 일반적으로 BFS를 돌 때는

x,y 좌표를 방문했는지 여부를 저장하면서 중복된 행동을 하지 않도록 합니다.

이 문제도 단지 x,y좌표를 방문했는지 여부와 동일하게

x,y좌표 방문 여부 + '말처럼 움직인 횟수' 라는 상태가 추가되어

중복된 행동을 하지 않으면서 BFS를 돈다고 생각하면 편합니다.

그리고 또한 이 문제를 왜 BFS로 해결 할 수 있냐면

원하는 답이 원숭이가 총 몇번 움직이는 행동을 했는 지 구하는 것이기 때문에

말처럼 움직이든 원숭이처럼 움직이든 특정 행동엔 관심없고

움직임 단계별로 일정하게 증가시키면서 답을 구하면 되기 때문에

너비우선탐색으로 해결 할 수 있습니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

struct Position {
    int x, y, k, d;

    Position(int a, int b, int c, int dd) {
        x = a, y = b, k = c, d = dd;
    }
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//horse
int hdx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int hdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

queue<Position> Q;

int K, W, H;
int arr[203][203];
bool vis[203][203][32];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> W >> H;

    // 행H , 열W
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> arr[i][j];
        }
    }

    Q.push({0, 0, 0, 0});

    while (!Q.empty()) {
        auto cur = Q.front();
        Q.pop();

        if (cur.x == H - 1 && cur.y == W - 1) {
            cout << cur.d << '\n';
            return 0;
        }

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (vis[nx][ny][cur.k] || arr[nx][ny] == 1) continue;

            vis[nx][ny][cur.k] = 1;
            Q.push({nx, ny, cur.k, cur.d + 1});
        }

        if (cur.k + 1 <= K) {
            for (int i = 0; i < 8; i++) {
                int nx = cur.x + hdx[i];
                int ny = cur.y + hdy[i];

                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (vis[nx][ny][cur.k + 1] || arr[nx][ny] == 1) continue;

                vis[nx][ny][cur.k + 1] = 1;
                Q.push({nx, ny, cur.k + 1, cur.d + 1});
            }
        }
    }

    cout << -1 << '\n';


    return 0;
}

https://www.acmicpc.net/problem/16946

#include <bits/stdc++.h>

using namespace std;

int n, m;

int arr[1001][1001];
vector<pair<int, int> > wall;
bool ch[1001][1001];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int num[1001][1001];
int marked[1001*1001]; // cnt[mark] = 개수 


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    for (int i = 0; i < n; i++) {

        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            arr[i][j] = s[j]-'0';
            if (arr[i][j]) wall.push_back({ i,j });
        }
    }

    int mark = 1;
	queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            
            if (arr[i][j] == 0 && num[i][j] == 0) {
				int cnt = 1;
                Q.push({ i,j });
                num[i][j] = mark;
                while (!Q.empty()) {
                    int x = Q.front().first;
                    int y = Q.front().second;
                    Q.pop();

                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];

                        if (nx < 0 || nx >= n || ny < 0 || ny >= m || num[nx][ny] || arr[nx][ny]) continue;
                        Q.push({ nx,ny });
                        cnt++;
                        num[nx][ny] = mark;
                    }
                }
				marked[mark] = cnt;
				mark++;
            }
        }
    }

    for (int i = 0; i < wall.size(); i++) {
        int x = wall[i].first;
        int y = wall[i].second;

        int wall_cnt = 1;
        set<int> s;

        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j];
            int ny = y + dy[j];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] > 0) continue;
            s.insert(num[nx][ny]);
        }

        for (auto k : s) {
            wall_cnt += marked[k];
        }
        arr[x][y] = (wall_cnt % 10);
    }




    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << arr[i][j];
        }
        cout << '\n';
    }
    return 0;
}

https://www.acmicpc.net/problem/2573

접근방법[알고리즘]

1. 빙산이 몇개의 덩어리로 이루어져있는지 BFS를 이용해 개수를 센다.

2. 빙산의 개수가 2개이상이거나 0이 아니면 빙산을 한차례 녹인다.

3. 1과 2를 반복한다.

주의할 점

빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
다음 빙산에 영향을 줘서 틀린다.
빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
적용 해주어야 한다.

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[301][301] ,t;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int Count() {
	int check[301][301];
	int ans = 1;
	memset(check, 0, sizeof(check));
	queue<pair<int, int> > Q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] > 0 && check[i][j]==0) {
				check[i][j] = ans;
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();

					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];
						if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == 0) continue;
						if (check[nx][ny] == 0) {
							check[nx][ny] = ans;
							Q.push({ nx,ny });
						}
					}
				}
				ans++;
			}
		}
	}
	return ans - 1;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<pair<int, int> > Q;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] > 0) Q.push({ i,j });
		}
	}


	while (1) {
		int area = Count();
		if (area >= 2) {
			cout << t << '\n';
			return 0;
		}
		else if (area == 0) {
			cout << 0 << '\n';
			return 0;
		}

		int s = Q.size();
		//빙산이 녹아 없어지는 경우 바로 0으로 만들어버리면
		//다음 빙산에 영향을 줘서 틀린다.
		//빙산이 0이 되는 경우는 따로 저장해뒀다가 큐를 한바퀴 다 돈다음
		//적용 해주어야 한다.

		vector<pair<int, int> > melt;
		for (int i = 0; i < s; i++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();

			int cnt = 0;
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny]>0) continue;
				cnt++;
			}

			if (cnt >= arr[x][y]) {
				melt.push_back({ x,y });
			}
			else {
				arr[x][y] -= cnt;
				Q.push({ x,y });
			}
		}
		for (int i = 0; i < melt.size(); i++) {
			arr[melt[i].first][melt[i].second] = 0;
		}

		t++;
	}

	return 0;
}

https://www.acmicpc.net/problem/11559

1.문제설명

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

12 * 6 으로 Input이 주어질 때

같은 색깔인 칸이 상하좌우로 인접하여 4개 이상 있다면 모두 터트려줍니다.

......
......
......
......
......
......
......
......
.Y....
.YG...
..YG..
..YGG.

더이상 터질 수 있는 뿌요가 없다면

중력에 의해 공중에 있는 뿌요는 밑으로 떨어지게 됩니다.

......
......
......
......
......
......
......
......
......
..G...
.YYG..
.YYGG.

다시 터트리고 채워주고 반복하면서

터트리는 과정을 몇번 할 수 있는지 세면 되는 문제입니다.

2.접근방법[알고리즘]

이 문제는 시뮬레이션 문제로 두가지 과정을 구현해주면 됩니다.

1. 뿌요 터트리기

2. 뿌요 떨어트리기

뿌요 터트리기는 BFS를 돌면서 같은 뿌요가 있다면 몇개있는지 세주고 4개 이상 있다면

같은 뿌요들을 저장해준뒤 char '.'로 바꿔주면 쉽게 구현할 수 있습니다.

뿌요 떨어트리기는 for문을 돌면서 맨 아래칸부터 시작하여 위칸을 돌면서

뿌요가 있다면 뿌요가 없는 맨 아래칸과 바꿔주면 됩니다.

처음 주어지는 INPUT이 중력에 의해 떨어진 상태가 아닐수도 있기 때문에

맨 처음 뿌요를 일단 다 떨어트리고 시작해야합니다.

3.문제풀이코드 C++

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

string arr[12];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

void fall() {
	for (int i = 0; i < 6; i++) {
		for (int j = 11; j >= 0; j--) {
			if (arr[j][i] == '.') {
				for (int k = j - 1; k >= 0; k--) {
					if (arr[k][i] != '.') {
						swap(arr[j][i], arr[k][i]);
						break;
					}
				}
			}
		}
	}
}


bool bomb() {
	bool ch[12][6];
	memset(ch, 0, sizeof(ch));
	queue<pair<int, int> > Q;
	bool bombed = false;

	for (int i = 0; i < 12; i++) {
		for (int j = 0; j < 6; j++) {

			if (ch[i][j] == 0 && arr[i][j] != '.') {

				vector<pair<int, int> > v;
				char color = arr[i][j];
				int cnt = 1;
				ch[i][j] = 1;
				v.push_back({ i,j });
				Q.push({ i,j });

				while (!Q.empty()) {
					int x = Q.front().first;
					int y = Q.front().second;
					Q.pop();


					for (int k = 0; k < 4; k++) {
						int nx = x + dx[k];
						int ny = y + dy[k];

						if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6 || ch[nx][ny] == 1) continue;
						if (arr[nx][ny] == color) {
							cnt++;
							ch[nx][ny] = 1;
							Q.push({ nx,ny });
							v.push_back({ nx,ny });
						}
					}
				}

				if (cnt >= 4) {
					bombed = true;
					for (int k = 0; k < v.size(); k++) {
						arr[v[k].first][v[k].second] = '.';
					}
				}
			}
		}
	}

	return bombed;
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);


	for (int i = 0; i < 12; i++) {
		cin >> arr[i];
	}
	// 필드에 뿌요를 모두 두고 일단 떨어트린다. 
	fall();

	//1.터트린다 - 개수 0이면 끝
	//2. 내린다
	//1.2 반복
	int ans = 0;

	while (1) {
		if (bomb()) {
			ans++;
			fall();
		}
		else {
			break;
		}
	}

	cout << ans << '\n';

	return 0;
}

https://www.acmicpc.net/problem/11724

1. 문제설명

무방향 그래프가 주어지고 노드와 간선간의 정보가 주어졌을 때

연결 요소 (Connected Component)의 개수를 구하는 문제입니다.

연결 요소의 개수는

서로 연결되어 있는 집합이 몇개인 지 구해야 합니다.

위 그림과 같은 경우 Connected Component는 2개 입니다.

2.접근방법[알고리즘]

먼저 떠오르는 해결 방법은

모든 노드 간선 정보를 바탕으로 그래프를 만들고

BFS나 DFS로 탐색하면서 방문한 노드를 체크하면서

방문하지 않은 새로운 노드를 발견할 때마다 정답으로 출력할 변수에 +1을 해주면 구할 수 있습니다.

한번 더 나아가면 Union & Find 알고리즘을 이용해

서로 연결되어있는 노드는 같은 집합으로 분류해주고

부모노드의 개수를 세면 집합의 개수를 알 수 있습니다.

Union & Find 알고리즘을 이용하면 BFS나 DFS보다 시간을 절약해서 풀 수 있습니다.

3.문제풀이코드 C++

1. Union & Find C++

#include <bits/stdc++.h>
using namespace std;

int n, m , unf[1001], ans;

int Find(int a) {
	if (a == unf[a]) {
		return a;
	}
	else {
		return unf[a] = Find(unf[a]);
	}
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);

	if (a > b) {
		swap(a, b);
	}

	if (a != b) {
		unf[a] = b;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i <= 1000; i++) {
		unf[i] = i;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Union(a, b);
	}

	// 부모 노드의 개수 == 같은 집합의 개수
	for (int i = 1; i <= n; i++) {
		if (unf[i] == i) ans++;
	}
	cout << ans << '\n';



	return 0;

}

2. BFS

#include <bits/stdc++.h>
using namespace std;

int n, m;

bool ch[1001];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	vector<int> map[1001];

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		map[a].push_back(b);
		map[b].push_back(a);
	}
	int ans = 0;
	queue<int> Q;
	for (int i = 1; i <= n; i++) {
		if (!ch[i]) {
			ans++;
			ch[i] = 1;
			Q.push(i);
			while (!Q.empty()) {
				int x = Q.front();
				Q.pop();
				for (int j = 0; j < map[x].size(); j++) {
					if (ch[map[x][j]] == 0) {
						ch[map[x][j]] = 1;
						Q.push(map[x][j]);
					}
				}
			}
		}
	}

	cout << ans << '\n';

	return 0;

}

https://www.acmicpc.net/problem/14923

문제 설명

https://dingcoding.tistory.com/95

백준 2206번 벽부수고 이동하기 문제와 똑같은 문제다.

벽을 부순 상태와 부수지 않은 상태를 나누어서 생각해야 한다.

설명은 위 링크를 참고

문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, hx, hy, ex, ey, arr[1003][1003], vis[1003][1003][2];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};

void print() {
	for (int k = 1; k >= 0; k--) {
		if (k == 1) {
			cout << "벽 뚫기 전 \n";
		}
		else {
			cout << "벽 뚫은 후 \n";
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << vis[i][j][k] << ' ';
			}
			cout << '\n';
		}
	}
	cout << "\n";
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	queue<Edge> Q;
	cin >> n >> m;
	cin >> hx >> hy;
	cin >> ex >> ey;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	vis[hx][hy][1] = 1;
	Q.push(Edge(hx, hy, 1));

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		/*print();*/

		if (x == ex && y == ey) {
			if (vis[x][y][1] == 0) {
				cout << vis[x][y][0]- 1;
			}
			else cout << vis[x][y][1] -1 ;
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];


			if (nx<=0 || nx>n || ny<=0 || ny>m) continue;

			// 벽 뚫을 수 있음
			if (op == 1) {
				if (arr[nx][ny] == 0 && vis[nx][ny][1]==0) {
					vis[nx][ny][1] = vis[x][y][1] + 1;
					//벽 방문 가능
					Q.push({ nx,ny,1 });
				}
				else if (arr[nx][ny] == 1) {
					vis[nx][ny][0] = vis[x][y][1] + 1;
					//이제 벽 방문 기회 없음 
					Q.push({ nx,ny,0 });
				}
			}
			else {//벽 뚫을 기회 없음 무조건 0으로만 다녀야함
				if (arr[nx][ny] == 0 && vis[nx][ny][0] == 0) {
					vis[nx][ny][0] = vis[x][y][0] + 1;
					Q.push({ nx,ny,0 });
				}
			}
		}



	}


	cout << -1;

	return 0;
}

https://www.acmicpc.net/problem/2206

1.문제설명

6 4
0100
1110
1000
0000
0111
0000

0은 이동할 수 있는 곳이고 1은 벽이다.

벽을 한번 부술 수 있을 때 (1,1)에서 (N,M) 까지 이동하는 최단 거리를 구해야한다.

2.접근방법[알고리즘]

맨 처음에는 없앨 벽을 선택하고, 그에 따른 최단 거리를 구해줬다.

하지만 이러면 계산량이 많아져서 시간초과가 된다.

https://www.acmicpc.net/board/view/27386

백준 게시판에 좋은 글이 있어서 첨부합니다.

요약하자면 벽을 부수기 전과 부순 후를 나누어서 생각해야 합니다.

이동하면서 현재 좌표는 벽을 부술 수 있는 지 없는지 상태를 저장해야합니다.

또 벽을 안 부수면서 이동할 때의 방문 기록을 체크해주는 배열과

벽을 부순 후 방문 기록을 체크해주는 배열을 따로 분리해 생각해야 합니다.

6 4
0100
1110
1000
0000
0111
0000

위 예제에 대해서 벽을 뚫기 전과 벽을 뚫은 이후를 따로 체크해주는 배열에 거리를 저장했습니다.

int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x]

위와 같은 방문기록을 체크해주는 vis 배열을 3차원으로 만들어

vis[x][y][1 == 벽을 뚫을 기회가 1번 있는 상태]

vis[x][y][0 == 벽을 뚫을 기회가 없는 상태, 이미 벽을 한번 뚫은 상태]

이렇게 저장해주어 BFS를 돌면서

벽을 뚫기 전까지는 vis[x][y][1]에 방문기록을 저장하다가

벽을 뚫는 일이 발생하면 그 이후부터는 vis[x][y][0]에 방문 기록을 저장해줍니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
string arr[1003];
int vis[1003][1003][2];
//vis[x][y][1 = 벽 뚫을 기회 1번 있음] , vis[x][y][0 = 벽 뚫을 기회 x] 
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

//void print() {
//	for (int k = 1; k >= 0; k--) {
//		if (k == 1) {
//			cout << "벽 뚫기 전 \n";
//		}
//		else {
//			cout << "벽 뚫은 후 \n";
//		}
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				cout << vis[i][j][k] << ' ';
//			}
//			cout << '\n';
//		}
//	}
//	cout << "\n";
//}

struct Edge {
	int x, y, op;
	Edge(int a, int b, int c) {
		x = a;
		y = b;
		op = c;
	}
};


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	queue<Edge> Q;
	Q.push(Edge(0,0,1));
	// 0에 좌표 방문 저장, 1에 벽 부쉇는지 저장 
	vis[0][0][1] = 1;
	vis[0][0][0] = 0;

	while (!Q.empty()) {
		int x = Q.front().x;
		int y = Q.front().y;
		int op = Q.front().op;
		Q.pop();

		//print();

		if (x == n - 1 && y == m - 1) {
			//도착 점 방문 시 이동하는데 걸린 거리 출력 
			if (vis[n - 1][m - 1][0] == 0)
				cout << vis[n - 1][m - 1][1];
			else
				cout << vis[n - 1][m - 1][0];
			return 0;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (op == 1) {
				//벽 부순적 없음 1도 방문 가능
				if (vis[nx][ny][1] == 0) {
					// 0 방문 할 떄 
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 1));
						vis[nx][ny][1] = vis[x][y][1] + 1;
					}
					else { // 1 방문할 떄 
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][1] + 1;
					}
				}
			}
			else {
				//벽 부순적 있음 
				//
				if (vis[nx][ny][0] == 0 && vis[nx][ny][1]==0) {
					if (arr[nx][ny] == '0') {
						Q.push(Edge(nx, ny, 0));
						vis[nx][ny][0] = vis[x][y][0] + 1;
					}
				}

			}
		}
	}

	cout << -1;
	return 0;
}

4. 2206 반례 

백준 2206번 벽부수기 반례, 테스트케이스 모음입니다.

1.

5 8
01000000
01010000
01010000
01010011
00010010

2.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

3.

3 3
011
111
110

4.

6 7
0000000
0111111
0100010
0101010
0101010
0001010

https://www.acmicpc.net/problem/17142

1.문제설명

7 3
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 2 0 1 1
0 1 0 0 0 0 0
2 1 0 0 0 0 2

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다.

0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 위치이다.

2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

2는 비활성화된 바이러스를 의미하고 2 중에서 m개를 선택해 바이러스를 활성화시킬 때

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

2.문제접근[알고리즘]

https://dingcoding.tistory.com/90

https://dingcoding.tistory.com/91

연구소 3번 문제는 연구소 1번 2번 문제와 비슷하나 가장 중요한 차이점은

초기에 모든 바이러스는 비활성화 상태라는 점이다.

문제에서 m개의 비활성화 바이러스를 선택해

벽을 제외한 모든 영역이 바이러스가 되는 최소 시간을 구해야한다.

모든 영역은 비활성화 바이러스거나 활성화 바이러스거나 상관 없이 바이러스이기만 하면 된다.

문제풀이과정

1. DFS를 통해 m개의 비활성화 바이러스를 선택해 활성화 바이러스로 만든다.

2. 선택된 활성화바이러스로 BFS를 하고, 벽을 제외한 모든영역에 바이러스를 퍼트리는 시간을 구한다.

3. DFS를 돌며 m개를 다르게 선택하며 최소 시간을 구해준다.

4. 바이러스를 어떤 방법으로도 전체 영역에 퍼트릴 수 없다면 -1, 아니면 최소시간을 출력한다.

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, m, arr[51][51], ans=INT_MAX, total_zero;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[51][51];

bool virus_select[11];
vector<pair<int, int> > virus;
queue<pair<int,int> > Q;

void BFS() {
	int count_zero = 0;

	//활성화된 바이러스 Q에 넣어줌 
	for (int i = 0; i < virus.size(); i++) {
		if (virus_select[i] == 1) {
			Q.push({ virus[i].first, virus[i].second});
			ch[virus[i].first][virus[i].second] = 1;
		}
	}

	int time = 0;
	while (!Q.empty()) {
		int cur_size = Q.size();

		/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

		/*같은 시간에 새로 추가된 모든 바이러스를 BFS로 탐색*/
		for (int j = 0; j < cur_size; j++) {
			int x = Q.front().first;
			int y = Q.front().second;
			Q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[nx][ny] == -1) continue; //벽이면 continue
				if (ch[nx][ny] == 0) { //비활성화된 바이러스, 0인 영역 모두 방문
					ch[nx][ny] = 1;
					Q.push({ nx, ny });
					if (arr[nx][ny] == 0) count_zero++; //0인 영역을 방문한 거라면 0인 영역에 바이러스 퍼진 갯수 세줌
				}
			}
		}
		time++;
	}

	//DFS에서 또 ch를 사용하므로 BFS함수 이전 원래 상태로 초기화
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ch[i][j] = 0;
		}
	}

}

void DFS(int cur, int L) {
	if (L == m) {
		BFS();
	}
	else {
		for (int i = cur; i < virus.size(); i++) {
			virus_select[i] = 1;
			DFS(i + 1, L + 1);
			virus_select[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			
			if (arr[i][j] == 2) virus.push_back({ i,j });
			else if(arr[i][j] == 0) total_zero++;
		}
	}

	DFS(0, 0);

	if (ans == INT_MAX) {
		cout << -1;
	}
	else {
		cout << ans;
	}

}

4.틀린 이유

1. 시간초과 이유 : 바이러스를 벽을 제외한 모든 영역에 퍼트렸는지 확인

/*0인 영역에 바이러스를 다 퍼트렸는지 체크*/
		if (total_zero == count_zero) {
			ans = min(time, ans);
			while (!Q.empty()) Q.pop();
			break;
		}

0의 개수를 세는 변수를 따로 설정해 바이러스가 된 0의 개수를 세서 비교했다.

이전에는 n*n 배열을 모두 탐색해 0이 있는지 없는지 확인해서 시간초과가 나서 틀렸다.

2. 비활성화된 바이러스도 바이러스다.

처음에 문제를 잘 이해하지 못해 모든 바이러스를 활성화 시켜야 끝나는 줄 알고 그렇게 했는데

비활성화 여부와 관계없이 모든 영역이 바이러스로 바뀌어있으면 BFS를 종료하면 된다.