[백준 - 1743] 음식물 피하기 (DFS)

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

1743번: 음식물 피하기

음식물이 땅에 놓여져 있으니까 그걸 피해가야합니다.

 

가장 큰 음식물은 뭘까요??? 찾아봅시다.

---

쉬운 문제입니다.

 

핵심 아이디어는 DFS입니다.

 

가장 큰 음식물 덩어리를 찾기만 하면 되는 거죠.

 

연결된 곳을 통해서 잘 탐색을 해주면 됩니다.

---

평소 문제처럼 탐색 기반이 되는 map을 제공하지 않습니다.

 

하지만 확인할 수 있는 예시와 좌표그림이 있기 때문에 똑같이 map이 있다고 생각하고 진행하면 됩니다.

 

1. DFS의 가장 기본적인 코딩으로 문제를 풀었습니다.

 

맨 처음에 좌표를 입력 받을 때 각 좌표를 벡터에 저장해두고 그 부분들을 모두 탐색하는 방식을 선택했습니다.

 

그리고 각 좌표를 DFS로 탐색한 이후에 최대 카운트를 비교해서 최댓값 갱신만 해주면 됩니다.

---

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int N, M;
int dirx[4] = {1,0,-1,0};
int diry[4] = {0,1,0,-1};
int map[101][101];
bool visit[101][101];
typedef pair<int, int> P; // (r,c) = (j, i)
vector<P> pos;
int cnt = 0;
int maxi = 0;

void dfs(int r, int c) {
    cnt++;
    visit[r][c] = true;
    
    for (int i = 0; i < 4; i++) {
        int nr = r + dirx[i];
        int nc = c + diry[i];
        
        if (nr >= 0 && nr <= N && nc >= 0 && nc <= M) {
            if (!visit[nr][nc] && map[nr][nc] == 1) {
                dfs(nr, nc);
            }
        }
    }
}

int main() {
    int K;
    
    cin >> N >> M >> K;
    
    for (int i = 0; i < K; i++) {
        int r, c;
        
        cin >> r >> c;
        
        map[r][c] = 1;
        
        pos.push_back(P(r,c));
    }
    
    for (int i = 0; i < pos.size(); i++) {
        cnt = 0;
        dfs(pos[i].first,pos[i].second);
          
        if (cnt > maxi)
            maxi = cnt;
    }

    
    cout << maxi << "\n";
}

 

 

깃허브 - https://github.com/cow-coding/algorithm/blob/master/BOJ/1743.cpp