C++ ) 백준 1743

 

 

문제

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

1743번: 음식물 피하기

N X M 맵에 상하좌우로 붙어있는 숫자들 중에 가장 큰 값(MAX)을 찾는 문제이다.

상하좌우 인접한 숫자들을 찾는 BFS를 사용해 풀었다.

 

로직

1. N X M 맵에 입력받기 (#은 1로, .은 0으로)

2. 좌표 y, x에 대하여 map이 '#'이거나 가보지 않은 곳이라면

checkmap에 가봤다고 표시하고 BFS 호출

3. Queue에 (y, x) 자신을 넣은 후에 인접한 수(tmpMAP)를 1로 초기화

4. 상하좌우 확인 후 (조건에 맞지 않으면 continue) checkmap에 미리 표시한 후 (갈거라고) Queue에 넣기를 반복

5. 함수 종료 이전에 도출한 tmpMax와 MAX 비교 후 갱신

 

내 코드

#include <iostream>
#include <queue>

using namespace std;

int map[101][101];
int checkmap[101][101];

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

int N, M, K;
int MAX = 0;

void BFS(int y, int x)
{
	pair<int, int> tmp;
	queue<pair<int,int>> Q;
	Q.push({y,x});
	int tmpMax = 1;

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

		int tmpy, tmpx;

		for(int i = 0; i < 4; i++)
		{
			tmpy = tmp.first + dy[i];
			tmpx = tmp.second + dx[i];

			if (tmpy < 0 || tmpy >= N || tmpx < 0 || tmpx >= M)
				continue;
			if (!map[tmpy][tmpx] || checkmap[tmpy][tmpx])
				continue;
			checkmap[tmpy][tmpx] = 1;
			tmpMax++;
			Q.push({tmpy, tmpx});
		}
		if (tmpMax > MAX)
			MAX = tmpMax;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> K;

	int y, x;

	for(int i = 0; i < K; i++)
	{
		cin >> y >> x;
		map[y - 1][x - 1] = 1;
	}
/*
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cout << map[i][j]<< " ";
		}
		cout << endl;
	}
*/
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			if (map[i][j] == 1 && checkmap[i][j] == 0) {
				checkmap[i][j] = 1;
				BFS(i, j);
			}
		}
	}
	cout << MAX;
}