[BAEKJOON] 1012_유기농 배추_Python

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

1012번: 유기농 배추

문제

 

 

 

문제 해설

(1) 배추가 심어진 x,y 좌표와 밭의 크기가 주어진다.
(2) 상하좌우로 이어진 배추가 몇그룹인지 반환하는 문제이다.

 

 

문제 풀이

dfs나 bfs로 완전탐색하면 된다. 나는 dfs로 풀었다.

"""
[parameter]
  visited: dictionary(int) - 배추가 심어진 좌표(key)와 방문여부 default0
  graph: list(N*M) - 밭 graph. 배추는 1, 아무것도 심기지 않은 땅은 0
  lettues: list - 탐색해야 할 배추리스트

"""

(1) 입력 받은 배추 좌표로 graph를 그리고, visited에 배추를 기록한다.
(2) visited의 key값을 lettues에 넣고 탐색을 시작한다.
(3) 이미 방문한 배추라면 pass하고 다음 배추로 넘어간다.
(4) 방문한적이 없다면, 새로운 배추 그룹이기에 answer에 +1을 해주고 dfs를 진행한다.

* dfs
1. 현재 x, y에 상하좌우 진행방향 좌표를 더해주어 새로 탐색할 후보 노드를 만든다. 현재 x, y 배추는 방문처리 해준다.
2. 후보노드들 중, M, N, 0에 초과, 미만되지 않고, 배추이면서, 방문하지 않는 노드들만 stack 담아준다.
3. 1, 2를 반복하다, 더이상 방문할 노드가 stack에 없다면 (2)~(4)로 돌아간다.

 

 

* 코드

from collections import defaultdict
from sys import stdin

T = int(stdin.readline())
upside = [[1, 0], [0, 1], [-1, 0], [0, -1]]
result = []
for t in range(T):
    M, N, K = list(map(int, stdin.readline().split()))
    visited = defaultdict(int)
    graph = [[0 for _ in range(M)] for _ in range(N)]
    answer = 0

    for k in range(K):
        y, x = map(int, stdin.readline().split())
        visited[(x, y)] = 0
        graph[x][y] = 1

    lettues = sorted(list(visited.keys()))
    for l in lettues:
        if visited[l] == 1:
            continue
        visited[l] = 1
        x, y = l
        answer += 1
        stack = []
        for u in upside:
            new = [x + u[0], y + u[1]]
            if new[0] > N or new[0] < 0 or new[1] > M or new[1] < 0:
                continue
            try:
                if graph[new[0]][new[1]] == 1:
                    stack.append(new)
            except:
                pass

        while len(stack) > 0:
            x_, y_ = stack.pop()
            if visited[(x_, y_)] == 1:
                continue
            visited[(x_, y_)] = 1
            for u in upside:
                new = [x_ + u[0], y_ + u[1]]
                if new[0] > N or new[0] < 0 or new[1] > M or new[1] < 0:
                    continue
                try:
                    if graph[new[0]][new[1]] == 1 and visited[(new[0], new[1])] == 0:
                        stack.append(new)
                except:
                    pass
    result.append(answer)

for a in result:
    print(a)