백준 1743 c++ "음식물 피하기" -PlusUltraCode-

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

 

[필자 사고]

단순한 BFS 탐색 문제다.

전체 배열을 조사해서 1번 및 방문을 안했을 시 BFS탐색을 시작한다.

탐색하면서 1이 갯수마다 maxCount를 갱신해주는 형태로 해당 문제를 타파했다.

 

아래는 자세한 코드 해설이다. 

[코드 해설]

1. Input()

• 입력을 처리하는 함수입니다.
• N, M, K를 입력받고, 격자판 크기에 맞게 visited와 arr 배열을 초기화합니다.
• K개의 음식물 위치를 받아 arr[a][b] = 1로 설정하여 해당 위치에 음식물이 있음을 표시합니다.

---

2. isInside(int sero, int garo)

• 주어진 좌표가 격자판 범위 내에 존재하는지 확인하는 함수입니다.
• 1 <= sero <= N이고 1 <= garo <= M인 경우에만 true를 반환합니다.

---

3. BFS(int sero, int garo)

• 주어진 위치에서 시작하여 너비 우선 탐색(BFS)으로 연결된 음식물 쓰레기의 크기를 측정합니다.
• 이미 방문한 위치는 탐색하지 않도록 하고, 음식물이 있는 위치(arr[nextSero][nextGaro] == 1)만 탐색합니다.
• BFS로 탐색한 후 연결된 음식물 쓰레기의 개수(count)를 세며, 현재까지 가장 큰 덩어리 크기보다 크면 resultCount를 갱신합니다.

---

4. Game_Start()

• 전체 격자판을 순회하면서 음식물이 있고 아직 방문하지 않은 위치에서 BFS를 호출합니다.
• 모든 덩어리를 검사한 후, 가장 큰 음식물 쓰레기 덩어리의 크기(resultCount)를 출력합니다.

---

5. main()

• 프로그램의 시작점입니다.
• Input()으로 데이터를 입력받고, Game_Start()를 호출하여 최종 결과를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

typedef pair<int, int> Node;
int N, M, K;
vector<vector<bool>> visited;
vector<vector<int>> arr;
int resultCount = 0;
void Input() {
	cin >> N >> M >> K;
	visited.assign(N + 1, vector<bool>(M + 1, false));
	arr.assign(N + 1, vector<int>(M + 1, 0));

	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		arr[a][b] = 1;
	}
	
}

bool isInside(int sero, int garo) {
	if (sero >= 1 && sero <= N && garo >= 1 && garo <= M)return true;
	return false;
}

void BFS(int sero, int garo) {
	queue<Node> myQueue;
	myQueue.push({ sero, garo });
	visited[sero][garo] = true;
	int count = 1;

	while (!myQueue.empty()) {
		int nowSero = myQueue.front().first;
		int nowGaro = myQueue.front().second;
		myQueue.pop();


		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];

			if (isInside(nextSero, nextGaro) == false)continue;
			if (visited[nextSero][nextGaro] == true) continue;
			if (arr[nextSero][nextGaro] == 1) {
				myQueue.push({ nextSero,nextGaro });
				visited[nextSero][nextGaro] = true;
				count++;
			}
		}

	}

	if (count > resultCount) {
		resultCount = count;
	}
}

void Game_Start() {
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= M; k++) {
			if (visited[i][k] == true)continue;
			if (arr[i][k] == 1) {
				BFS(i, k); 
			}
		}
	}

	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}