[바킹독 BFS] 1926 그림부터 BFS 예제 복습

[바킹독 BFS] 1926 그림부터 BFS 예제 복습

바킹독님 BFS 강의 링크는 https://blog.encrypted.gg/941

[실전 알고리즘] 0x09강 - BFS

 

백준 1926번는 Flood Fill 문제

정리) Flood Fill의 기본적인 문제

BFS 돌리면서 pop한 만큼 그림의 길이를 알고,

BFS의 새로운 시작점이 될 수 있는지는 조건문 검사해서 하는 것.

max로 갱신해준다.

 

참고 코드 - 다음 링크를 참고하세요!

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/1926.cpp

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

 

VScode에서 안 돌아간 이유는 내가 틀려서 그랬다. 저번에 구현했는데 실력 다시 바닥 되었네

좀 부족한 부분-BFS의 시작점을 찾는 곳에서 실력이 부족해 miss 남

 그 miss난 부분

if (board[i][j] == 0 || vis[i][j]) continue; // 빨간색이거나 방문한 곳은 시작점 안 돼
			num++; // 그 외의 조건에서는 그림의 시작점이 될 수 있으니 그림 개수 늘려줘

 

 

2178번 미로 탐색 문제

정답 코드 링크) https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/1926.cpp

전체 코드 (P.S Visual Studio를 쓸 때는 프로젝트 생성하고... 그래야지 빌드 버튼 찾기 쉽다ㅋㅋ)

/* 클론 코딩하면서 놓치는 거 최소화 하기*/

클론 코딩하면서 놓치는 거 많았다... 다시 하렴;;

 

 

내가 헷갈렸던 포인트:현재 시작 칸은 dist 배열 0으로 두고 시작하지만, 마지막에 거리 출력 시 dist 배열 + 1로 해준다.

0인 시점도 한칸 쭉이니까, 그 네모칸을 생각해봐라!

cout << dist[n - 1][m - 1] + 1; // 문제의 특성상 거리 + 1이 정답

그리고 숫자 붙여서 받는 방법 때문에 이리저리 고민하다가 다음과 같이 하면 되는 것을 알았다.

/* string 배열로 숫자 붙여서 받는 방법 뒷처리도 고민*/
	for (int i = 0; i < n; i++)
		cin >> board[i];

뒷처리는 그냥 '1' 써주면 된다.

 

ppt 참고) dist가 0 이상 찍히면 방문했던 친구들 왜냐-처음에 -1로 초기화 하기 위해서 fill 함수를 썼다.

 

여기서 딸렸던 것은 구현력이네. 그리고 클론 코딩 한다 하면 잘 따라쳐... 실수만 안 해도 maximum 6개월 번다 생각한다.

 

 

그 다음으로

7576번 토마토 문제

시간복잡도 관련 바킹독님 말씀

 각 익은 토마토들에 대해 해당 위치를 시작점으로 하는 BFS를 한 번씩 다 돌리는 방법을 떠올릴 수 있지만, 그러면 BFS의 시간복잡도가 O(NM)이고 익은 토마토 또한 최대 NM개가 있을 수 있으니 총 O(N2M2)이 되어 시간 내로 해결이 안될 것입니다. 과연 어떻게 문제를 해결할 수 있을까요?

 

자세한 거는 바킹독님 강의를 참고하자

 

문제 조건 중에 주의 깊게 봤던 거

입력) 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸

출력)여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

그러면 입력 받고 시작점이 되는 익은 토마토는 큐에 넣어주는게 BFS 국룰이고

아직 익지 않은 토마토는 거리 배열 dist에다가 -1을 넣어주는게 맞어.

for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cin >> board[i][j];
      if(board[i][j] == 1)
        Q.push({i,j});
      if(board[i][j] == 0)
        dist[i][j] = -1;
    }
  }

토마토 없는 칸은 제외하고 하면 돼

 

그리고 미로 탐색 문제 기본 응용하는 게 나와~ 자세한 거는 dist 배열 사용하는 코드 참고

 

 

dist 배열 + 1이 정답이 아니고 dist 배열이 정답인 이유) 이미 익은 토마토 = 0일, 이와 관련해서 코드 좀 돌려보기

처음부터 친구부터 먼저 dist가 0으로 초기화 됩니다 <- 확인 차원으로 한 번 찍어보기

그러고 그 옆에 있는 친구는 1일, 2일... 이렇게 걸리죠.

바킹독님 토마토 슬라이드 참고해보기

#include <iostream>
#include <queue>

using namespace std;
#define X first
#define Y second
int board[1002][1002];
int dist[1002][1002];
int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

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

	cin >> m >> n;
	queue<pair<int, int>> Q;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) /* 익은 토마토이면*/
				Q.push({ i,j });
			if (board[i][j] == 0) /* 익지 않은 토마토면*/
				dist[i][j] = -1; /* dist[i][j]=-1; 하는 이유) 미로 탐색 문제 참고하세요 */
		}
	}
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			/* BFS 공식 */
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0) continue; /* 이미 거리 배열에 들어간 친구는 초기화 하지 마*/
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx, ny });
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] == -1) {
				cout << -1;
				return 0;
			}
			ans = max(ans, dist[i][j]);
		}
	}
	cout << ans;

}

 

내가 이해가 필요한 부분) ...이제 거리가 0인 칸들은 큐에서 다 빠졌고, 순차적으로 1인 칸들을 pop할텐데 잘 생각해보면 1인 칸들을 pop하는 동안 거리가 2인 칸들이 쭉 추가될 것입니다.

이거는 BFS 공식에 의한 거... pop하고 네 방향 돌아서 push 해주는 일 하잖아!

while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			/* BFS 공식 */
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0) continue; /* 이미 거리 배열에 들어간 친구는 초기화 하지 마*/
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx, ny });
		}
	}

 

다음 문제로는 4179번 불! 문제

불! 문제 풀기 전에 거리 배열 dist를 사용하는 문제-2178번 미로 탐색 문제를 먼저 내 방식으로 구현해보자.

그리고 불! 문제로 돌아가서 불의 BFS, 지훈이의 BFS 돌리고, 칸에 따라서 몇 시간 뒤에 불이 붙는지(0시간~?시간) 거리 배열인 dist 배열을 써준다.

그리고 BFS 결과에 따른 그걸 조건에 따라 처리. 지훈이가 갈 수 있는지 없는지 말이다. 그래서 골드 문제인듯하다.

 

처음에 미로의 끝점을 [R-1][C-1] 인덱스로 잡아놓은게 내 잘못이다.

틀린 코드를 보면

#include <iostream>
#include <queue>
#include <string>

#define X first
#define Y second
using namespace std;

string board[1002];
int fire[1002][1002];
int jihun[1002][1002];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int R, C;

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

	cin >> R >> C;

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

	/* -1로 초기화 해주기 */
	for (int i = 0; i < R; i++) {
		fill(fire[i], fire[i] + C, -1);
		fill(jihun[i], jihun[i] + C, -1);
	}
	/* 지훈이와 불의 BFS queue 각각 선언*/
	queue<pair<int, int>> Q1;
	queue<pair<int, int>> Q2;

	/*불 찾아서 큐에 넣어주기*/
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'F') {
				Q1.push({ i,j });
				fire[i][j] = 0;
			}
		}
	}

	/* 지훈이 찾아서 큐에 넣어주기*/
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (board[i][j] == 'J')
			{
				Q2.push({ i,j });
				jihun[i][j] = 0;
			}
		}
	}

	/*각자 bfs 돌려주기*/
	while (!Q1.empty()) {
		auto cur = Q1.front(); Q1.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if (board[nx][ny] == '#' || fire[nx][ny] >= 0 ) continue;
			fire[nx][ny] = fire[cur.X][cur.Y] + 1;
		}

	}

	while (!Q2.empty()) {
		auto cur = Q2.front(); Q2.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];

			if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
			if (board[nx][ny] == '#' || jihun[nx][ny] >= 0) continue;
			jihun[nx][ny] = jihun[cur.X][cur.Y] + 1;
		}
	}

	/*impossible 검거*/
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++)
		{
			fire[i][j] >= jihun[i][j];
			cout << "IMPOSSIBLE";
			return;
		}
	}

	/* 미로의 탈출 위치를 특정 짓는 다음 코드는 잘못됨*/
	cout << jihun[R-1][C-1];
}

인덱스의 범위가 초과되면 탈출 성공인데 이것을 간과하고... 풀었던 문제처럼 풀어버렸다! 그럼 안 되고, 다른 방식을 써야한다!

그리고 불과 지훈이는 실시간으로 이동한다는 점을 고려해서

불의 BFS -> 지훈이 BFS 돌릴 때 불의 조건도 넣어준다.

그렇게 해서 짠 코드는 바킹독님 링크 참고

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/4179.cpp

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

 

숨바꼭질 문제는 백트래킹 하고... 하련다!

 

오늘 소감) 갈 길 멀다... 알고리즘의 왕도는? 모르겠다 초보 이제 0.3일차 노베이스

오랜만에 visual studio 쓰니까 불편해. 빌드 누르고 F5 누르면 실행된다. 단축키 외워라

모르는 거는 빨간색으로!

깃허브에 업로드 할 까...ㅋㅋㅋ 작심일일 일지도ㅜ

나중에 종만북도 풀고... 잘 하고 싶어!