1926

날짜 : 2023. 2. 23

사용 언어 : python

 

문제

 

 

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())  # 도화지 세로, 가로
paper = list()
res = list()
for _ in range(n):
    paper.append(list(map(int, sys.stdin.readline().split())))  # 그림 입력
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
cnt = 0
wid = 0


def bfs(r, c):
    #print(r, c)
    w = 1
    q = deque()
    q.append([r, c])
    paper[r][c] = 2  # 방문처리
    while q:
        nx, ny = q.popleft()
        for i in range(4):  # 연결탐색
            x = nx + dx[i]
            y = ny + dy[i]
            if x in range(n) and y in range(m):
                if paper[x][y] == 1:  # 조건 만족(그림)
                    q.append([x, y])  # 큐에 삽입
                    paper[x][y] = 2  # 방문처리
                    w += 1  # 넓이 증가
    return w


for i in range(n):
    for j in range(m):
        if paper[i][j] == 1:  # 그림 발견
            cnt += 1
            wid = max(wid, bfs(i, j))

if cnt == 0:  # 그림이 없는 경우
    print(0)
    print(0)
else:
    print(cnt)
    print(wid)

"""for i in paper:
    print(i)
print(res)"""

 

 

풀이

- 일반적인 그래프 탐색을 이용해서 문제를 풀이한다.

 

 

알게된 점

- 무심코 BFS로 풀었다가 메모리 초과가 발생해서 이를 최소화시키기 위해 이중 for 문에서 리스트 대신 변수 2개를 통해 문제를 해결했다.

 

 

참고 사이트

-