[boj 1012, 2606, 7576/C++] 유기농 배추, 바이러스, 토마토(bfs와 dfs)

 

이번 주는 그래프 이론과 깊이 우선탐색(dfs), 넓이 우선 탐색(bfs)에 대해서 살펴보았다.

 

먼저 그래프는 사물이나 개념 간의 연결관계를 수학적 모델로 단순화하여 표현한 것으로

프로그래밍으로 이를 표현하기 위한 방법으로는 대표적으로 인접 행렬과 인접 리스트 방식이 있다.

문제의 조건에 따라 효율적인 방식을 골라 이용하는 것이 중요하다.

 

인접 행렬은 인접 리스트보다 비교적 dense한 조건 하에 사용하는 것이 더욱 효율적이고 반대로 인접 리스트는 sparse한 조건 하에 사용하는 것이 더욱 효육적이라고 볼 수 있다.

 

그리고 각각의 방식으로 표현된 그래프는 그 탐색을 위해 dfs와 bfs 방식을 사용할 수 있다.

 

먼저 dfs(깊이 우선 탐색) 방식은 가지 하나를 길게 탐색에 이용하는 방식으로 이해했다. 이를 구현하기 위해서 방문 여부를 체크하기 위한 배열이나 구조체 내부의 checker가 필요하고, 하나의 요소와 이어진 또 다른 요소를 아직 방문하지 않았다면 해당 요소를 방문, 그리고 또 해당 요소와 이어진 다른 방문하지 않은 요소를 방문하는 형태로 더이상 탐색할 노드가 없다면 이전 요소와 이어진 또 다른 요소를 방문하는 식의 탐색을 진행한다. 

 

bfs(넓이 우선 탐색) 방식은 queue를 이용한 구현이 가장 보편적이다. 하나의 요소와 이어진 모든 요소를 탐색하고 그 다음 level로 넘어가 다른 요소를 방문하는 식의 탐색을 진행한다. 

 

말로는 그 개념이 어려울 수 있으나 직접 그래프에서 이를 그려보면 이해가 더 빠르게 된다.

 

그래서 위의 개념을 이용해 문제를 풀어보았다.

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

1012번: 유기농 배추

유기농 배추 문제는 가로세로 길이가 많이 길지 않아서 인접행렬 방식을 선택했고, dfs를 이용한 탐색을 통해 문제를 해결했다.

 

#include <iostream>
#include <cstring> //for using memset

using namespace std;

int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
int arr[50][50];
int visited[50][50];
int t, m, n, k;
int x, y, cnt;

void dfs(int i, int j) { //재귀호출을 통한 dfs 구현
    for (int s = 0; s < 4; s++) {
        int nx = j + dx[s], ny = i + dy[s];
        if (ny < 0 || ny >= n || nx < 0 || nx >= m)
            continue;
        if (arr[ny][nx] && !visited[ny][nx]) {
            visited[ny][nx] = 1;
            dfs(ny, nx);
        }
    }
}

int main() {
    cin >> t;
    while (t) {
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
        cnt = 0;
        cin >> m >> n >> k;
        for (int i = 0; i < k; i++) { //dfs 탐색 전 arr 세팅
            cin >> x >> y;
            arr[y][x] = 1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] && !visited[i][j]) {
                    cnt++;
                    visited[i][j] = 1;
                    dfs(i, j);
                }
            }
        }

        cout << cnt << '\n';
        t--;
    }
}

 

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

2606번: 바이러스

바이러스 문제는 이번에는 인접 리스트와 dfs 방식을 이용해 문제를 해결해보았다.

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

int n, k, cnt;
vector<int> list[101]; //컴퓨터별로 이어져있는 컴퓨터를 기록하는 인접리스트
int warm[101]; //감염여부를 체크

void dfs(vector<int> p) {
	for (int i = 0; i < (int)p.size(); i++) {
		if (!warm[p[i]]) {
			warm[p[i]] = 1;
			cnt++;
			dfs(list[p[i]]);
		}
	}
}

int main() {
	cin >> n >> k;
	for(int i = 0; i<k; i++){
		int a, b;
		cin >> a >> b;
		list[a].push_back(b); //undirected graph라서 양쪽 다 추가
		list[b].push_back(a);
	}
	warm[1] = 1;
	dfs(list[1]);
	cout << cnt;
}

 

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

7576번: 토마토

 

마지막 문제인 토마토 문제는 처음에 이것도 dfs로 풀면 안되나? 생각했는데, 하루가 지날수록 동시에 그 옆의 토마토가 익어가는 level적인 특성이 있어서 dfs로 푸니까 시간초과가 났다. 그래서 bfs로 이를 해결해보았다!

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0,0,-1,1 };
int box[1001][1001];
queue<pair<int, int>> q;

int m, n, i, j;
int tom, day;

void bfs() {
	while (!q.empty()) {
		int x = (q.front()).second, y = (q.front()).first;
		q.pop();
		for (int s = 0; s < 4; s++) {
			int nx = x + dx[s], ny = y + dy[s];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (box[ny][nx] == 0) {
				box[ny][nx] = box[y][x] + 1;
				tom--;
				q.push(make_pair(ny, nx));
				if (day < box[ny][nx]) day = box[ny][nx];
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> m >> n;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			cin >> box[i][j];
			if (box[i][j] == 1) {
				q.push(make_pair(i, j));
			}
			else if (box[i][j] == 0) {
				tom++;
			}
		}
	}
	if (tom == 0) { 
		cout << 0;
		return 0;
	}

	bfs();
	if (tom != 0) cout << -1;
	else cout << day-1;
}