[백준/boj] 1012번: 유기농 배추 | C++

 

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

1012번: 유기농 배추

문제풀이 핵심

실수 포인트

 

1. 행 열 입력이 반대였는데 (열 행 순으로 입력받음) 빨리풀다가 발견 못하고..쓸데없이 오래 해멘.. 

문제를 잘 읽자 ! 예시의 입력값을 잘 보자, 가로길이 세로길이 그림으로 그려두자

 

2. 배추밭 담는 배열이랑 방문 여부 담을 배열을 테스트 케이스마다 초기화 해줘야되는 것을 간과함 - > 전역번수로 선언함

---

문제풀이 코드

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
//1을 찾아서 시작점으로
//최소 개수- > bfs

#define X first
#define Y second

int k; // 심어진 배추 개수
int t,m,n; // 테스트케이스 개수
queue<pair<int,int>> Q;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){ // 테스트 케이스만큼 반복
        int board[52][52]={0 ,}; // 배추 위치 담음
        bool vis[52][52]={0 ,};//방문 여부 확인 => bool 형식으로 할것

        int result =0;
        cin >> m>>n>>k;
        // m = 열 개수 , n = 행 개수
        for(int i = 0;i<k;i++){
            int x, y;
            cin >> x >> y;
            board[y][x] = 1; // 배추 위치에 1을 심어줌
        }
        for(int i = 0; i<n; i++){
            for(int j = 0; j<m; j++){
                if(board[i][j]==1 && vis[i][j] == 0){ //방문 안한 배추 발견시
                    result++;
                    vis[i][j] =1;
                    Q.push({i,j});
                    while(!Q.empty()){ //큐가 비어있는게 아닌경우
                        pair<int,int> cur = Q.front(); 
                        Q.pop(); //pop하는거 까먹고 안써줬당 주의주으이
                        for(int k = 0; k<4;k++){
                            int nx = cur.X + dx[k];
                            int ny = cur.Y + dy[k]; 
                            
                            if(nx<0|| nx>=n|| ny <0||ny>=m) continue; // m = 가로길이 = 열개수 
                            if(vis[nx][ny]==1|| board[nx][ny] ==0) continue; //board 가 배추가 아닌경우 continue 하는거임
                            
                            vis[nx][ny]=1;
                            Q.push({nx,ny});
                        }
                    } 
                }
            }
        }
        cout << result<<'\n';
    }
}

 

---

로직 설명

각 테스트 케이스마다 열과 행을 입력받고, 배추 개수만큼 반복하며 배추가 있는 좌표에 1을 넣어준다

그리고 2중 배열을 순회하며 방문안한 배추를 발견하면 그곳을 시작점으로 잡고 bfs를 돈다

bfs 를 한번 돌 때마다 (각 배추 덩어리의 시작점을 발견할 때 마다 result 값을 +1 해준다. result는 최종 출력값임)

bfs를 돌면서 현재 좌표의 상하좌우 좌표를 확인한다

다음 행 열이 범위를 벗어나는지 먼저 확인하고 범위를 벗어나면 상하좌우 좌표중 다음 좌표 살펴보기

다음 행 열이 이미 방문한 곳이거나 배추가 없는 곳이면 역시나 다음 좌표 살펴보기

 

위의 두 조건을 잘 지나왔으면 시작점과 이어진 배추라는 의미이므로 vis =1 로 방문표시 해주고 Q에 좌표를 넣는다

이제 Q에서 하나씩 빼가면서 상하좌우 확인하고~계속 bfs 를 돈다

그리고 테스트 케이스 하나하나가 끝나기 전에 필요한 배추 개수(result) 출력해주고 다음 테스트 케이스로 넘어간다

 

---

 

마무리

그냥 쉬운 bfs 문제인 줄 알았는데 사소한 실수가 1시간동안의 삽질을 만들어낸 ..ㅜㅜ

문제 잘읽자.. 행-열순 입력인지 열-행순 입력인지..

가로길이 = 열 개수 세로길이 =행 개수 써두고 문제 풀기! 괜히 헷갈리지 말구

 

그리고 Q pop 하는것 잊지 말구

 

그리고 각 반복문마다 초기화 해줘야 하는 변수들이 무엇인지 잘 확인하자