백준 1926 python [그림]

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

DFS

import sys
sys.setrecursionlimit(10**6)

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()
    
def input():
    return sys.stdin.readline()

def dfs(x, y, count):
    visited[y][x] = True
    
    for i in range(4):
        newX = x + moveX[i]
        newY = y + moveY[i]
        
        if(visited[newY][newX] == True):
            continue
        
        if(newY >= n or newY < 0 or newX >= m or newX < 0):
            continue
        
        if(maps[newY][newX] == 1):
            visited[newY][newX] = True
            count = dfs(newX, newY, count)
            
    return count + 1
            


n, m = map(int, input().split(" "))
maxWidth = 0
cnt = 0
moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
maps = []
visited = [[False] * (m+1) for _ in range(n+1)]
for _ in range(n):
    maps.append(list(map(int, input().split(" "))))


for y in range(n):
    for x in range(m):
        if(visited[y][x] == False and maps[y][x] == 1):
            cnt += 1
            result = dfs(x, y, 0)
            
            if(result > maxWidth):
                maxWidth = result

print(cnt)
print(maxWidth)

BFS

import sys
from collections import deque

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()
    
def input():
    return sys.stdin.readline()

def bfs(x, y):
    Q = deque()
    Q.append((x, y))
    visited[y][x] = True
    nodeCnt = 1
    
    while Q:
        nX, nY = Q.popleft()
        
        for i in range(4):
            newX = nX + moveX[i]
            newY = nY + moveY[i]
            
            if(visited[newY][newX] == True):
                continue
            
            if(newY >= n or newY < 0 or newX >= m or newX < 0):
                continue
            
            if(maps[newY][newX] == 1):
                visited[newY][newX] = True
                Q.append((newX, newY))
                nodeCnt += 1
                
    return nodeCnt

n, m = map(int, input().split(" "))
maxWidth = 0
cnt = 0
moveX = [1, 0, -1, 0]
moveY = [0, -1, 0, 1]
maps = []
visited = [[False] * (m+1) for _ in range(n+1)]

for _ in range(n):
    maps.append(list(map(int, input().split(" "))))
    

for y in range(n):
    for x in range(m):
        if(visited[y][x] == False and maps[y][x] == 1):
            cnt += 1
            result = bfs(x, y)
            
            if(result > maxWidth):
                maxWidth = result
                
print(cnt)
print(maxWidth)

---

BFS와 비슷하게 모든 노드의 위치를 방문하면서 검사해주면 된다.

뭔가 BFS보다 손이 덜 가는듯 하다.

제출하다가 RecursionError 에러가 났었는데
sys.setrecursionlimit(10**6)를 추가해서 해결했다.