[BaekJoon] 백준 1012번 유기농 배추(C++, Python)

 

[BaekJoon] 백준 1012번 유기농 배추

 

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

 

 

내코드

 

- 기본적인 bfs문제

- 단지 테스트 케이스가 여러개 있어서 매번 초기화 해줘야한다는걸 주의해야했다.

- 처음에 vector를 초기화를 안해줘서 계속 에러가 났다.

- 다른 문제들에서는 인접 행렬(Adjacency Matrix)로 입력이 주어졌지만 여기선 인접 리스트(Adjacency List)로 쓰면 편한 형태로 주어졌다. 그래도 인접 행렬로 풀었다.

- 아래는 아이패드에 정리한 내용.

 

백준 1012번 유기농배추.pdf

4.48MB

 

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

int T, m, n, k, cnt;
int arr[50][50];
bool visited[50][50];
queue<pair<int, int>> qu;

void isNear(int a, int b) {
	if (a < 0 || b < 0 || a >= n || b >= m) return;
	if (visited[a][b] == false && arr[a][b] == 1) {
		qu.push(make_pair(a, b));
		visited[a][b] = true;
	}
}

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

	cin >> T;
	while (T--) {
		cin >> m >> n >> k;
		//initialize
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i][j] = 0;
				visited[i][j] = false;
			}
		}
		vector <pair<int, int>> loc;
		cnt = 0;
		for (int i = 0; i < k; i++) {
			int a, b;
			cin >> a >> b;
			arr[b][a] = 1;
			loc.push_back(make_pair(b, a));
		}
		for (int i = 0; i < k; i++) {
			int a = loc.at(i).first;
			int b = loc.at(i).second;
			if (visited[a][b]) continue;
			qu.push(make_pair(a, b));
			visited[a][b] = true;
			cnt++;
			while (!qu.empty()) {
				pair<int, int> cur = qu.front();
				a = cur.first;
				b = cur.second;
				qu.pop();
				isNear(a, b - 1);
				isNear(a + 1, b);
				isNear(a - 1, b);
				isNear(a, b + 1);
			}
		}
		cout << cnt << "\n";
	}
	
	return 0;

 

파이썬으로 다시 품

from collections import deque


T = int(input())


def bfs():
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    M, N, K = map(int, input().split())
    visited = [[False for _ in range(N)] for _ in range(M)]

    # init
    position = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        x, y = list(map(int, input().split()))
        position[x][y] = 1

    # bfs
    n = 0
    queue = deque()
    for i in range(M):
        for j in range(N):
            if position[i][j] == 0 or visited[i][j]:
                continue
            queue.append([i, j])
            n += 1
            while queue:
                x, y = queue.pop()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if nx < 0 or nx >= M or ny < 0 or ny >= N:
                        continue
                    if visited[nx][ny] or position[nx][ny] == 0:
                        continue
                    visited[nx][ny] = True
                    queue.append([nx, ny])
    print(n)


for _ in range(T):
    bfs()