Algorithm-BOJ-1743

10 Mar 2019

Reading time ~2 minutes

BOJ-1743-음식물 피하기

이 문제 역시 다른 대표적인 DFS문제들과 같은 유형이다. 특히 유기농배추와 매우 비슷하다. 이 문제는 쉽게 말하면 음식물들의 집합 중에서 가장 큰 집합을 찾는 문제이다.

따라서 모든 배열을 돌면서 음식물이 있지만 아직 방문하지 않은 음식물이 있으면 방문해서 음식물의 개수를 확인한다. 메인에서 음식물이 있지만 아직 방문하지 않았다는 것은 새로운 음식물 집합을 뜻하므로 해당 row, col을 기록하고

for(int i=1; i<=N; i++) {
        for(int j=1; j<=M; j++) {
            if(map[i][j] && !visited[i][j]) {
                ansR = i;
                ansC = j;
                trash[ansR][ansC] = 0;
                dfs(i, j);
            }
        }
    }

배열을 확인하는 dfs 함수에서는 동서남북 4방향에 음식물이 있는지 확인해서 count를 해주면 된다.

int mR[4] = { -1, 0, 1, 0 };
int mC[4] = { 0, 1, 0, -1 };

void dfs(int row, int col) {
    visited[row][col] = true;
    trash[ansR][ansC]++;
    
    for(int i=0; i<4; i++) {
        int nextR = row + mR[i];
        int nextC = col + mC[i];
        
        if(nextR >= 1 && nextC >= 1 && nextR <= 100 && nextC <= 100) {
            if(map[nextR][nextC] && !visited[nextR][nextC]) {
                dfs(nextR, nextC);
            }
        }
    }
}

풀이보기

```c++
    #include <iostream>
    
    bool map[101][101];
    bool visited[101][101];
    int trash[101][101];
    
    int N, M, K;
    int r, c, ansR, ansC;
    
    int mR[4] = { -1, 0, 1, 0 };
    int mC[4] = { 0, 1, 0, -1 };
    
    void dfs(int row, int col) {
        visited[row][col] = true;
        trash[ansR][ansC]++;
        
        for(int i=0; i<4; i++) {
            int nextR = row + mR[i];
            int nextC = col + mC[i];
            
            if(nextR >= 1 && nextC >= 1 && nextR <= 100 && nextC <= 100) {
                if(map[nextR][nextC] && !visited[nextR][nextC]) {
                    dfs(nextR, nextC);
                }
            }
        }
    }
    
    int main(int argc, const char * argv[]) {
        scanf("%d %d %d", &N, &M, &K);
        
        while (K--) {
            scanf("%d %d", &r, &c);
            map[r][c] = true;
        }
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=M; j++) {
                if(map[i][j] && !visited[i][j]) {
                    ansR = i;
                    ansC = j;
                    trash[ansR][ansC] = 0;
                    dfs(i, j);
                }
            }
        }
        
        int ans = 0;
        
        for(int i=1; i<=100; i++) {
            for(int j=1; j<=100; j++) {
                ans > trash[i][j] ? ans : ans = trash[i][j];
            }
        }
        
        printf("%d\n", ans);
    
        
        return 0;
    }
```

c++Algorithm