코테 백준 1926 실버1

백준 1926

bfs,dfs 개념은 알고있었지만 문제를 푸는데 어려움이 조금있었다. 그래서 간단한 bfs문제를 풀면서 풀이방법에 대해 익숙해지기로 했다. bfs특징은 특정위치에서 주변의 위치의 값으로 점점 퍼져가는것이다. 이 문제를 보면 graph의 값이 1일때만 cnt를 증가하고 주변의 1인게 없다면 다시 0부터 시작한다. bfs는 자료구조 que에 특화되있어서 deque를 사용했다. bfs문제를 풀 때 동서남북 방향으로 이동하기때문에 x,y의 배열도 생성해주었다. 이러한 점이 bfs 문제 풀때 공통점인것 같다.

import sys
from collections import deque
input=sys.stdin.readline

n,m=map(int,input().split())
graph=[]

for i in range(n):
    graph.append(list(map(int,input().split())))

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def bfs(graph,i,j):

    que=deque()
    que.append((i,j))
    graph[i][j]=0
    cnt=1

    while que:
        a,b=que.popleft()
        for i in range(4):
            x=a+dx[i]
            y=b+dy[i]
            if x<0 or x>n-1 or y<0 or y>m-1:
                continue
            if graph[x][y]==1:
                cnt+=1
                graph[x][y]=0
                que.append((x,y))
    return cnt
total=[]
for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            total.append(bfs(graph,i,j))

if len(total)==0:
    print(len(total))
    print(0)
else:
    print(len(total))
    print(max(total))