[그래프 #3] Flood Fill을 이용한 문제 풀이 방법

Flood Fill

N차원 공간에서의 BFS라고 볼 수 있음

 

1. queue 준비

• 시작 노드 queue에 삽입
• (cycle이 생길 시) visited 준비
• 좌표를 준비

1. 시작 노드를 예약후 시작
2. BFS 동작.

• queue에 가야하는 / 예약된 노드가 있는 동안 반복
• now -> 지금 방문하는 노드를 queue의 맨 앞에서 pop
• now에서 갈수 있는 노드들을 판단
  • (방향 배열 필요) → 문제에서 주어질 것
  • 갈 수 있다면, queue에 새로 삽입 + 예약 (방문 기록)

 

 

일반적인 Flood Fill 공식

struct Node{   // 좌표 값을 다룰 것이기 때문에, Node 구조체 구현
	int y;
	int x;
};

int xdir[4] = {-1,0,1,0};
int ydir[4] = {0,-1,0,1};

void bfs(int y, int x){

	queue<Node>q;

	q.push({ y, x }); // 배열로 넣으면, 선언 순서에 맞춰 저장
	
	int visited[5][5] = { 0, };
	visited[y][x] = 1;  // 시작 노드 방문 기록

  	while (!q.empty()){
		
		Node now = q.front();
		q.pop();
		
		for (int i = 0; i < 4; i++){
			int ny = now.y + ydir[i];
			int nx = now.x + xdir[i];
			
			// 방향 배열이 들어갈 시, 무조건 범위체크 해야 함
			if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
			
			// 이미 방문했거나, 방문이 예약된 상태라면 
			if (visited[ny][nx] == 1) continue;

			visited[ny][nx] = 1;
			q.push({ny, nx});
		}
}

 

날짜를 체크하는 Flood Fill 코드

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

struct Node {
	int y;
	int x;
};

int arr[5][5];

int xdir[4] = { -1,0,1,0 };
int ydir[4] = { 0,-1,0,1 };

void bfs(int y, int x) {

	queue<Node>q;

	q.push({ y, x }); // 배열로 넣으면, 선언 순서에 맞춰 저장

	int visited[5][5] = { 0, };
	visited[y][x] = 1;  // 시작 노드 방문 기록

	int day = 0;      
	int cursize = 0;  // queue에 새로 push 된 개수를 세주기 위함

	while (!q.empty()) {

		Node now;

		cursize = q.size();

		for (int c = 0; c < cursize; c++){
			now = q.front();
			q.pop();

			for (int i = 0; i < 4; i++) {
				int ny = now.y + ydir[i];
				int nx = now.x + xdir[i];

				// 방향 배열이 들어갈 시, 무조건 범위체크 해야 함
				if (ny < 0 || nx < 0 || ny >= 5 || nx >= 5) continue;
				
                		// 이 부분에 특정 좌표에 도달할 시, return day+1; 로도 구현 가능
                
				if (visited[ny][nx] != 0) continue;
                
				visited[ny][nx] = visited[now.y][now.x] + 1;
			
				q.push({ ny, nx });
			}
		}

	}
    
    return;
    
}