유기농 배추_ 백준 1012번

2020-04-02 · 배운 것 · 3분 읽기

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

1012번: 유기농 배추

1. 풀이 방법

일반적인 dfs풀이 + dfs가 몇번 호출되었나 세어주면 된다.
주의할 사항은 y, x순 입력이 아니라 x, y순 입력이라는것과 map과 visit배열을 testcase가 바뀔때마다 초기화시켜주어야 하는것 정도이다.

2. 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[52][52];
bool visit[52][52];
int k, n, m;

void mapVisitErase()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			map[i][j] = visit[i][j] = 0;
}

void dfs(int y, int x)
{
	visit[y][x] = true;

	if (y - 1 >= 0)
		if (map[y - 1][x])
			if (visit[y - 1][x] == false)
				dfs(y - 1, x);

	if (y + 1 < n)
		if (map[y + 1][x])
			if (visit[y + 1][x] == false)
				dfs(y + 1, x);

	if (x - 1 >= 0)
		if (map[y][x - 1])
			if (visit[y][x - 1] == false)
				dfs(y, x - 1);

	if (x + 1 < m)
		if (map[y][x + 1] )
			if (visit[y][x + 1] == false)
				dfs(y, x + 1);
}


int main()
{
	int testcase;
	cin >> testcase;

	for (int c = 0; c < testcase; c++)
	{
		cin >> m >> n >> k;
		
		//map에 지렁이 넣기
		int y, x;
		for (int kc = 0; kc < k; kc++)
		{
			cin >> x >> y;
			map[y][x] = 1;
		}

		//지렁이 수 세기
		int cnt = 0;
		for(int i =0; i<n; i++)
			for (int j = 0; j < m; j++)
			{
				if (map[i][j] == 1 && visit[i][j] == false)
				{
					//dfs
					dfs(i, j);
					cnt++;
				}
			}

		cout << cnt << '\n';

		mapVisitErase();
	}

	return 0;
}

3. 후기

최근에 풀던 카카오 문제들이 손대는것마다 좌절감만 안겨줘서 좀 쉬운 문제를 풀어보자 해서 풀어보게 되었다.
물론 쉬운문제지만 혹시 좌표를 헷갈린다거나 초기화를 제때 안해주면 주어지는 테스트 케이스로는 판별할수 없어 삽질할수도 있다.