이번 문제는 처음 시도에는 깊이우선탐색으로 접근하였다. 방문처리 리스트 대신에 paper리스트 자체에서 확인한 인덱스를 0으로 바꿔주면서 그 영역의 넓이까지 카운팅하는 방식으로 재귀함수를 호출하였다. 이 방식으로 빠르게 해결할 수 있었다.

import sys
sys.setrecursionlimit(10**9)
def dfs(y, x, cnt):
    paper[y][x]=0
    for i in range(4):
        ny=y+dy[i]
        nx=x+dx[i]
        if ny>=0 and nx>=0 and ny<n and nx<m:
            if paper[ny][nx]==1:
                cnt=dfs(ny, nx, cnt+1)
    return cnt
n, m=map(int, input().split())
paper=[]
for _ in range(n):
    paper.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
answer=0
cnt=0
for i in range(n):
    for j in range(m):
        if paper[i][j]==1:
            answer=max(answer, dfs(i, j, 1))
            cnt+=1
print(cnt)
print(answer)

그러나 이 과정에서 메모리 초과가 계속 발생하였다. 메모리를 줄이는 방법으로 코드를 수정하고 제출하기를 여러번 시도했지만 도저히 메모리 초과 문제를 해결할 수 없었다. 그래서 찾아본 결과 입력의 크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500)이기 때문에 재귀로는 해결할 수 없다는 사실을 알게 되었다. DFS를 공부하고 있었기 때문에 DFS로 풀고 싶었지만 더 빠른 BFS로 풀게 되었다.

BFS도 DFS로 접근한 방식과 별반 다르지는 않았다. DFS에서 재귀호출 하는 대신에 BFS에서는 큐에 값을 넣어주는 방식으로 탐색을 진행하게 된다.

• 큐를 사용하기 위해 deque를 가져온다.
• bfs함수를 y, x를 인자로 갖도록 선언한다.
  -> paper[y][x]를 0으로 갱신한다.
  -> q를 큐로 선언한다.
  -> q에 (y, x)를 넣는다.
  -> 영역의 넓이를 구하기 위한 변수 cnt를 1로 선언한다.
  -> q가 비어있지 않을동안 반복하는 while문을 돌린다.
  --> y, x에 q.popleft()의 반환값을 저장한다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny에 y+dy[i]를 저장한다.
  ---> nx에 x+dx[i]를 저장한다.
  ---> 만약 ny, nx가 0보다 크거나 같고, ny가 n보다 작고, nx가 m보다 작고, paper[ny][nx]가 1일 경우,
  ----> q에 (ny, nx)를 넣어준다.
  ----> paper[ny][nx]를 0으로 갱신한다. (방문처리)
  ----> cnt를 1 증가시킨다. (영역의 크기 증가)
  -> cnt를 반환한다.
• n과 m을 입력받는다.
• 도화지의 그림 정보를 입력받을 리스트 paper를 선언한다.
• n번 반복하는 for문을 돌린다.
  -> paper를 입력받는다.
• 4가지 이동 방향의 정보를 저장할 리스트 dy, dx를 선언하고 4가지 방향을 짝지어 저장한다.
• answer를 0으로 선언한다.
• cnt를 0으로 선언한다.
• n번 반복하는 i에 대한 for문을 돌린다.
  -> m번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 paper[i][j]가 1일 경우,
  ---> answer를 answer, bfs(i, j)중 더 큰 값으로 갱신한다.
  ---> cnt를 1 증가시킨다.
• cnt를 출력한다.
• answer를 출력한다.

Code

from collections import deque
def bfs(y, x):
    paper[y][x]=0
    q=deque()
    q.append((y,x))
    cnt=1
    while q:
        y, x=q.popleft()
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if ny>=0 and nx>=0 and ny<n and nx<m and paper[ny][nx]==1:
                q.append((ny, nx))
                paper[ny][nx]=0
                cnt+=1
    return cnt
n, m=map(int, input().split())
paper=[]
for _ in range(n):
    paper.append(list(map(int, input().split())))
dy=[0, 0, -1, 1]
dx=[1, -1, 0, 0]
answer=0
cnt=0
for i in range(n):
    for j in range(m):
        if paper[i][j]==1:
            answer=max(answer, bfs(i, j))
            cnt+=1
print(cnt)
print(answer)