[백준] 1012 파이썬(python) : 유기농 배추

1012번 : 유기농 배추

 

 

dfs 나의풀이)

import sys
sys.setrecursionlimit(10**9) #1
t = int(sys.stdin.readline())
for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())
    graph = [ [0]*m for _ in range(n) ] #2
    visit = [ [False]*m for _ in range(n) ] #2
    cnt = 0
    dx = [ 0, 0, -1, 1 ] #3
    dy = [ -1, 1, 0, 0 ]
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1 #4
    def dfs(x, y):
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and visit[nx][ny] == False:
                    visit[nx][ny] = True
                    dfs(nx, ny)

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visit[i][j] == False:
                visit[i][j] = True #5
                dfs(i, j)
                cnt += 1 #6
    print(cnt)

 

#1 : 재귀호출 제한해제

#2 : 입력받을 그래프와 방문처리할 리스트 생성

#3 : 방향벡터

#4 : 가로길이, 세로길이 순서로 입력을 받으니 graph[b][a]로 입력

#5 : 첫 호출위치 방문처리

#6 : 끝나면 cnt +1

 

---

 

bfs를 이용한 풀이)

 

 

큰 틀은 dfs와 유사하지만 재귀가 아닌 큐를 이용했다는 점에서 차이가 있습니다.

 

 

import sys
from collections import deque
t = int(sys.stdin.readline())
for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().split())
    graph = [ [0] * m for _ in range(n) ]
    for _ in range(k):
        a, b = map(int, sys.stdin.readline().split())
        graph[b][a] = 1
    visit = [ [False]*m for _ in range(n) ]
    dx = [ 0, 0, -1, 1 ]
    dy = [ -1, 1, 0, 0 ]
    cnt = 0

    def bfs(x, y):
        q = deque()
        q.append((x, y))
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i] # 3
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1 and visit[nx][ny] == False: #1
                    visit[nx][ny] = True
                    q.append((nx, ny))
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1 and visit[i][j] == False:
                cnt += 1
                bfs(i, j) # 2
    print(cnt)

 

#1에서 0 <= nx < n이 되는 이유 (m이 아닌 n인 이유) -> x가 가로라고 착각해서 그렇습니다.

#2에서 i는 for i in range(n):이니까 세로축이고, j는 가로축입니다. 일반적인 (x, y)라고 생각해서 "가로, 세로"라고 생각하시면 안됩니다.

#3에서도 nx는 세로축의 이동이고, 그래서 #1에서 nx는 0 <= nx < n이 됩니다.

 

수학에서 좌표계와 2차원 배열에서 위치가 다르기 때문에 헷갈릴 수 있습니다.

 

비슷한 문제: 2667번, 18405번