1012번: 유기농 배추

 

 

 

풀이

 

dfs 와 bfs로 풀 수 있습니다.

입력 방법이 조금 헷갈리는 문제입니다.

 

 

 

dfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 dfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 dfs를 재호출 합니다.

 

주위에 1이 없다면 배추흰지렁이가 필요한 부분을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

...

 

 

bfs

...

아직 방문하지 않은 graph[i][j]가 1인곳에서 bfs을 호출하고 graph[x][y] = 0 으로 방문처리 해줍니다.

 

상,하,좌,우 에 대한 다음위치를 특정해주고 graph[nx][ny] == 1 이라면 queue에 nx, ny를 삽입하고 graph[i][j] = 0 으로 방문 처리합니다.

 

quque가 비게 된다면 배추흰지렁이가 필요한  부분을 다 탐색한것이므로 cnt를 1 증가 시켜줍니다. 

...

 

 

 

파이썬 dfs

import sys
sys.setrecursionlimit(1000000)


def dfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    graph[x][y] = 0

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
            dfs(nx, ny)


t = int(input())
for _ in range(t):

    m, n, k = map(int, sys.stdin.readline().split())
    graph = [[0] * m for _ in range(n)]
    cnt = 0

    for k in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(i, j)
                cnt += 1
    print(cnt)

 

 

 

파이썬 bfs

from collections import deque
import sys


def bfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    graph[x][y] = 0
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = 0
                queue.append((nx, ny))

t = int(input())
for _ in range(t):

    m, n, k = map(int, sys.stdin.readline().split())
    graph = [[0] * m for _ in range(n)]
    cnt = 0

    for k in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)