개요

백준 1743번: 음식물 피하기

• 입력
  첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

  좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

• 출력
  첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

접근 방법

1. [백준 1012번] 과 같은 문제다.
   차이점은 이 문제에서는 각 컴퍼넌트의 노드의 갯수를 알아야 한다.
2. dfs(int x, int y)함수에서 노드갯수 저장하는 변수를 선언한 후, 노드 갯수를 반환하도록
   함수의 자료형을 int로 선언해준다.
   각 dfs에서 반환해준 노드 갯수를 다 더하면 해당 컴퍼넌트의 총 노드갯수가 나온다.

코드

#include<iostream>
#include<algorithm>

using namespace std;
int height = 0, width = 0, garbage = 0;
int field[101][101];
bool visit[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void input() {
	int r=0, c = 0;
	cin >> height >> width >> garbage;
	for (int i = 0; i < garbage; i++) {
		cin >> r >> c;
		field[r][c] = 1;
	}
	fill(&visit[1][1],&visit[100][100],false);
}
/// <summary>
/// (x,y)좌표와 이어진 노드들을 dfs로 탐색한 후, 노드갯수를 더한 후 반환.
/// </summary>
/// <param name="좌표 x"></param>
/// <param name="좌표 y"></param>
/// <returns>노드갯수를 리턴</returns>
int dfs(int x, int y) {
	//각 컴퍼넌트의 노드갯수
	int Nodes = 1;
	//방문 했다면 return
	if (visit[x][y] == true) return 0;
	//방문 했으므로 true로 표기
	visit[x][y] = true;
	int nextA = 0, nextB = 0;
	for (int i = 0; i < 4; i++) {
		nextA = x + dx[i];
		nextB = y + dy[i];
		//x,y의 상하좌우 값이 각각 범위 안에 있고, 해당 값에 쓰레기가 존재할 경우  field안에 x,y로 넣어놨누;
		if (nextA >= 1 && nextB >= 1 && nextA <= height && nextB <= width && field[nextA][nextB])
		{
			//방문한 곳이면 패스 
			if (!visit[nextA][nextB]) {
				//해당 dfs에서의 노드 리턴값을 노드에 더해준 후
				Nodes += dfs(nextA, nextB);
			}
		}
	}
	//노드 갯수 리턴
	return Nodes;
}

void solution() {
	//최대컴퍼넌트의 노드갯수
	int maxComponent = 0;
	for (int i = 1; i <= height; i++) {
		for (int j = 1; j <= width; j++) {
        	//(i,j)좌표에 방문 안 했고, 쓰레기가 있다면
			if (!visit[i][j] && field[i][j] == 1) {
            	//해당 좌표가 포함한 컴퍼넌트의 노드갯수를 maxComponent와 비교해서 더 큰값 저장
				maxComponent=max(dfs(i, j),maxComponent);
			}
		}
	}
	cout << maxComponent;
}

int main() {
	input();

	solution();
}

문풀후생

dfs 함수에서 쓰레기가 있는 지 검사하는 부분인

if (nextA >= 1 && nextB >= 1 && nextA <= height && nextB <= width && field[nextA][nextB])

여기서 field [nextA][nextB] 가 아니라 field [x][y]로 조건 적어서 답이 계속 이상하게 나왔다..
배열의 행렬값으로 들어가는 변수들도 다시 한번 체크해야겠다.