[백준] 1012 유기농 배추.py

pseeej·2021년 8월 12일

Algorithms DFS Graph baekjoon

문제 링크 : https://acmicpc.net/problem/1012

💡 아이디어

문제를 어떤 방식으로 해결하려 했는지 그 과정을 적어주세요. 초기에 접근한 방법과 최종 접근이 차이가 없으면 한개만 적어도 됩니다.

초기 접근

원래는 어떻게 하려고 했냐면,,, ~~근데 지나고 나서 생각해보니 그것도 맞을 것 같은데 그냥 DFS 구현을 제대로 못한 것 같다.~~ 방문 기록을 위한 배열을 새로 생성하지 않고! 그냥 방문한 곳에 새로운 값을 넣어주려고 했다. 배열 최대 크기가 2500이니깐 3000으로~~(나름 머리 썼다고 생각했음ㅋ)~~ 해서 지렁인가 애벌렌가가 갈 수 있는 한 영역은 모두 똑같은 수로 구성되게! 하려고 했다. 그러고 최종적으로 거기서 가장 큰 수-3000-1해서 개수 세려고 했고,,, 그러다가 처참하게 틀렸습니다를 맞이했고,,, 구현 실패로 무한루프에 걸리기도 했다.
사실 이 방법으로 두 번이나 해봤는데 안되길래 솔루션 검색도 해봤다. 근데 코드 딱 보니깐 뭔가 지저분하길래 제대로 안 읽었음ㅋ

최종 접근

그러던 중,,, 맹진이에게 절망적인 카톡을 보냈고~ 맹진이가 힌트를 줘서 그걸로 풀었다. 그렇게 해서 나온 방법은 바로!

위는 그냥 넣어보고 싶어서ㅋ 맹진이가 하는 얘기 들으면서 좀 쓰다가,,, 혼자 머리 또 굴려서?
1. 방문 여부 기록해둘 visited 배열 생성
2. 방문하지 않았는데 배추가 있을 경우
  1. cnt값++
  2. 상하좌우로 돌면서(충돌 검사 필수) 방문 안 한 배추 있는지 찾아보고
  3. 있으면 그 배추 위치 방문 기록해두기
  4. 배추가 없다 → 종료
  5. 배추 있는데 이미 방문했다 → 종료
  
  뭐 이런 내용,,,

📋 사용 스펙

어떤 알고리즘 또는 기법을 사용해 문제를 해결했는지 알려주세요

👨🏻‍💻 👩‍💻 코드

#include <iostream>
using namespace std;

int** visited;
int** arr;
int M, N;

// visited랑 arr배열 재사용 위해 초기화해주는 함수
void init(int row, int col) {
	visited = new int* [row];
	arr = new int* [row];

	for (int i = 0; i < row; i++) {
		visited[i] = new int[col];
		arr[i] = new int[col];
	}

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			visited[i][j] = 0;
			arr[i][j] = 0;
		}
	}
}

void dfs(int r, int c) {
	if (arr[r][c] == 0)	// 배추 없잖아!
		return;
	if (arr[r][c] == 1 && visited[r][c] == 1)	// 배추 있는데 이미 방문한 곳
		return;
	if (arr[r][c] == 1 && visited[r][c] == 0) {	// 배추 있는데 아직 방문을 안 했네!
		visited[r][c] = 1;	// 방문기록 남기고 갑니다요,,,~

		// 여기서 나오는 조건문은 다 충돌검사 위한 거
		// 그리고 상하좌우 재귀로 탐색하기
		if (r - 1 >= 0)
			dfs(r - 1, c);
		if (r + 1 < N)
			dfs(r + 1, c);
		if (c - 1 >= 0)
			dfs(r, c - 1);
		if (c + 1 < M)
			dfs(r, c + 1);
	}

	return;
}

int main() {

	int T;
	cin >> T;

	while (T--) {
		int K;

		// ㅋㅋ 아니 보통 행-열 이렇게 주는데 얘넨 반대로 주더라
		cin >> M >> N >> K;

		// 난 열-행보단 행-열맨이라 ㅎㅅㅎ
		init(N, M);
		int cnt = 0;

		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			arr[y][x] = 1;	// 배추 있는 곳 위치 표시
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// 배추 있는데 방문 안 한 곳만
				if (arr[i][j] == 1 && visited[i][j] == 0) {
					cnt++;	 // 개수 더해주고
					dfs(i, j);	// 거기서부터 탐색할랭
				}
				else;
			}
		}

		cout << cnt << "\n";

	}

	return 0;
}