1012_유기농 배추

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

1012번: 유기농 배추

 

 

 

이전 문제와 똑같은 유기농 배추 문제이다. 

 

역시 이차원 그래프, visited배열, 밭의 지도를 그리고 이어져있는 밭의 개수를 새면 된다.

 

 

t = int(input())
dx = [0,1,0,-1]
dy = [1,0,-1,0]

for _ in range(t):
    m,n,k = map(int,input().split())

    farm = [ [ 0 for _ in range(m) ] for __ in range(n) ]
    graph = [[[] for _ in range(m)] for __ in range(n)]
    visited = [ [False] * m for _ in range(n) ]
    cnt = 0


    for __ in range(k):
        x,y = map(int,input().split())
        farm[y][x] = 1

    for i in range(n):
        for j in range(m):
            for k in range(4):
                try:
                    if farm[i][j] and farm[i+dx[k]][j+dy[k]]:
                        if i + dx[k] >= 0 and j + dy[k] >= 0:
                            graph[i][j].append([i+dx[k],j+dy[k]])
                except:
                    continue

    def dfs(x,y):
        visited[x][y] = True

        for a,b in graph[x][y]:
            if not visited[a][b]:
                dfs(a,b)

    for i in range(n):
        for j in range(m):
            if not visited[i][j] and farm[i][j]:
                dfs(i,j)
                cnt+=1

    print(cnt)

dfs 와 bfs 모두 풀어보았다.

 

from collections import deque
t = int(input())
dx = [0,1,0,-1]
dy = [1,0,-1,0]

for _ in range(t):
    m,n,k = map(int,input().split())
    farm = [ [ 0 for _ in range(m) ] for __ in range(n) ]
    graph = [[[] for _ in range(m)] for __ in range(n)]
    visited = [ [False] * m for _ in range(n) ]
    cnt = 0

    for __ in range(k):
        x,y = map(int,input().split())
        farm[y][x] = 1

    for i in range(n):
        for j in range(m):
            for k in range(4):
                try:
                    if farm[i][j] and farm[i+dx[k]][j+dy[k]]:
                        if i + dx[k] >= 0 and j + dy[k] >= 0:
                            graph[i][j].append([i+dx[k],j+dy[k]])
                except:
                    continue

    def bfs(x,y):
        q = deque([[x,y]])
        visited[x][y] = True
        while q:
            tmp = q.popleft()
            for a,b in graph[tmp[0]][tmp[1]]:
                if not visited[a][b]:
                    q.append([a,b])
                    visited[a][b]=True

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