개요

백준 1012: 유기농 배추

• 입력
  입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

• 출력
  각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

접근방법

1. 그래프 관련 문제에 익숙치 않아서 노드를 어떻게 짜고 인접한 부분은 어떻게 표시해야할지
   몰랐다.

class Graph {
private:
	//노드 갯수
	int N;
	//인접 노드 리스트
	vector<vector<int>> adj;
	//방문 여부
	vector<int> visited;
public:
	Graph(int N) :N(N) {
		adj.resize(N);
		visited.resize(N);
		fill(visited.begin(), visited.end(), false);
	}

	//간선 추가 양방향이므로 u의 인접리스트와 v의 인접리스트에 동시추가
	void addEdge(int u, int v) {
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	//각 노드의 인접 간선들을 정렬
	void sortGraph() {
		for (int i = 0; i < N; i++) {
			sort(adj[i].begin(), adj[i].end());
		}
	}

	//dfs방식으로 순회하며 
	void dfs(int current) {
		//current번째는 방문!
		visited[current] = true;
		//해당 current노드의 인접 노드들을 foreach문으로
		for (int elem : adj[current]) {
			//인접노드가 방문을 안한 노드라면
			if (!visited[elem]) {
				//해당 노드에서 다시 dfs
				dfs(elem);
			}
		}
	}

	int dfsAll() {
		//컴퍼넌트가 몇개있는지 조사
		int component = 0;
		for (int i = 0; i < N; i++) {
			//방문하지 않았을 경우
			if (!visited[i]) {
				component++;
				dfs(i);
			}
		}
		return component;
	}
};

이런식으로 그래프를 짜봤으나, 문제는 행렬칸에 있는 노드값들을 어떤식으로 여기에 적용시킬지 고민을 하다 못 풀었다.
1번과 2번노드가 붙어있다라고 생각해봤으나 2차원 배열에서 붙어있는 값을 몇번과 몇번이라고 정의를 어떻게 할지 모르겠다.

2. 찾아본 방법은 dfs방식을 이용한 재귀함수로 배추가 1인 점에서 상하좌우를 다 탐색 후,
   범위안에 존재하며 배추가 있는 점에서 다시 dfs를 호출하는 방식이다.

코드

#include<iostream>

using namespace std;

int Tot=0, width=0,height=0,X=0,Y=0, K=0;
//전체 필드
int field[51][51];
//방문한 필드
bool visited[51][51];
//(x-1,y),(x+1,y),(x,y-1),(x,y+1)로 나누기위함
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

//(a,b) 점에 대해 dfs수행
void dfs(int a, int b) {
	//a,b방문했다면 return
	if (visited[a][b]) return;
	//방문 안했다면 방문했다고 체크해주기
	visited[a][b] = true;
	for (int i = 0; i < 4; i++) {
		//x-1,x+1,x
		int nextA = a + dx[i];
		//y,y-1,y+1
		int nextB = b + dy[i];
		//나눴을때 행과 열이 범위 안에 있으면서 배추가 있는 칸일때 dfs 다시 시행 
		if (nextA >= 0 && nextB >= 0 && nextA < height && nextB < width && field[nextA][nextB]) {
			dfs(nextA, nextB);
		}
	}
	return;
}


void solution() {
	int Ans = 0;
	//방문 배열 false로 초기화
	fill(&visited[0][0], &visited[50][50],false);
	
	//행
	for (int i = 0; i < height; i++) {
		//열
		for (int j = 0; j < width; j++) {
			//배추가 있고, 방문하지 않았다면
			if (field[i][j] == 1 && !visited[i][j]) {
				//컴퍼넌트 갯수 추가하고 dfs시작
				Ans++;
				//dfs함수 호출
				dfs(i, j);
			}
		}
	}
	cout << Ans<<'\n';

}

void input() {
	cin >> Tot;
	for (int i = 0; i < Tot; i++) {
		cin >> width>> height>>K;
		//field 0으로 초기화
		fill(&field[0][0], &field[50][50], 0);
		for (int i = 0; i < K; i++) {
				cin >> X >> Y;
				field[Y][X] = 1;
		}
		solution();
	}
}


int main() {
	input();
}

문풀후생

상하좌우를 체크할때
나는 늘 x와 y조건 체크하고 dfs(x-1,y), dfs(x+1,y) dfs(x,y-1) dfs(x,y+1)
이렇게 네 개 다 작성하였었다.
하지만 참고한 코드에선 저런식으로 (-1,1,0,0) (0,0,-1,1) 이렇게 두개의 배열
생성 후 반복문을 이용해 조합을 하였는데 상당히 놀라웠다.

하나 배워갔다는 생각이 든다.

레퍼런스

참고한 블로그 글