[C] 백준 - 1012번: 유기농 배추

5월 19일(금) - 그래프와 순회 (1012번)

1012번: 유기농 배추

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 직전에 풀었던 "2667번: 단지 번호 붙이기" 문제의 풀이와 기본적으로 비슷한 풀이를 예상

- dfs 방식으로 풀이를 진행하며

- 입력은 K개의 x,y 좌표값들을 받아서 1을 넣은 뒤, 1이 들어간 좌표이며 방문한 적이 없으면 dfs 재귀호출

- 출력은 testcase 마다 변수 count를 통해 배추흰지렁이의 마리 수를 저장하고, 출력한다

- dx와 dy 배열을 이용해서 상하좌우로 연결되어있는 값들을 확인한다

[C] 백준 - 2667번: 단지번호붙이기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

		for (int j = 0; j < 51; j++)
		{
			for (int k = 0; k < 51; k++)
			{
				field[j][k] = 0;
				visited[j][k] = 0;
			}
		}

1. 모두 K개의 x,y 좌표들을 입력받기 전 과정에서, 위의 코드 부분 없이 제출했더니 오답

-> 다른 풀이들을 검색해본 결과 dfs방식은 동일하지만, 새로운 testcase에 들어가기전에 init 과정이 더 있음

-> 따라서 위의 코드를 추가한 결과 정답처리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int field[51][51];
int visited[51][51];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int T, M, N, K;

void dfs(int y, int x)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_y < 0 || next_x >= M || next_y >= N)
		{
			continue;
		}
		if (field[next_y][next_x] == 1 && visited[next_y][next_x] == 0)
		{
			dfs(next_y, next_x);
		}
	}
}

int main(void)
{
	scanf("%d", &T);

	for (int i = 0; i < T; i++)
	{
		scanf("%d %d %d", &M, &N, &K);

		int x, y;
		int count = 0;
		for (int j = 0; j < 51; j++)
		{
			for (int k = 0; k < 51; k++)
			{
				field[j][k] = 0;
				visited[j][k] = 0;
			}
		}

		for (int j = 0; j < K; j++)
		{
			scanf("%d %d", &x, &y);
			field[y][x] = 1;
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				if (field[i][j] == 1 && visited[i][j] == 0)
				{
					dfs(i, j);
					count++;
				}
			}

		}
		printf("%d\n", count);
	}

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ