백준 1012번 유기농 배추

문제 링크입니다: https://www.acmicpc.net/problem/1012

쉬운 문제였는데 사소한 부분에서 고생한 문제였습니다.

저는 그래프에서 좌표를 (y, x) 기준으로 문제를 푸는데 문제는 (x, y) 기준으로 제시되어서 좌표를 입력 받을 때

        int x, y;

        cin >> x >> y;

lettuce[y][x] = 1;

이런 식으로 입력받아야했습니다.

물론, (x, y) 기준으로 문제를 푸시는 분들은 고려하지 않아도 되는 문제입니다.

이후에는, 간단한 DFS로 문제를 해결하면 됩니다!

결국, 컴포넌트가 몇개인지 구하는 문제였습니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 50;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int M, N, K;

int lettuce[MAX][MAX];

bool visited[MAX][MAX];

 

void DFS(int y, int x)

{

        //기저 사례

        if (visited[y][x])

                 return;

 

        visited[y][x] = true;

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) //범위 내에 있고

                         if (lettuce[nextY][nextX])//이동

                                 DFS(nextY, nextX);

        }

}

 

int main(void)

{

        int T;

        cin >> T;

 

        for (int i = 0; i < T; i++)

        {

                 memset(visited, false, sizeof(visited));

                 memset(lettuce, 0, sizeof(lettuce));

                 cin >> M >> N >> K;

 

                 for (int j = 0; j < K; j++)

                 {

                         int x, y;

                         cin >> x >> y;

                         lettuce[y][x] = 1;

                 }

 

                 int cnt = 0;

                 for(int j = 0; j < N; j++)

                         for(int k = 0; k < M; k++)

                                 //아직 보호받지 못한 배추가 있으면 DFS 진행

                                 if (lettuce[j][k] && visited[j][k] == false)

                                 {

                                          DFS(j, k);

                                          cnt++; //필요한 지렁이 숫자 증가

                                 }

 

                 cout << cnt << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~