[Baekjoon] 1926_그림

Silver I

문제(출처: https://www.acmicpc.net/problem/1926)

---

<그림>

문제 

 

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

 

입력

 

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

 

 

출력 

 

첫째 줄에는 그림의 개수, 둘째 줄에는 그중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

 

 

문제 풀이

   - my solution (Python)

import sys
from collections import deque

if __name__=='__main__':
    n,m=map(int,sys.stdin.readline().split()) # 세로 크기, 가로 크기

    graph=[]
    visited=[[0]*m for i in range(n)] # 방문 여부
    area=[] # 그림의 넓이
    for i in range(n): # 그림의 정보
        graph.append(list(map(int,sys.stdin.readline().split())))

    for i in range(n):
        for j in range(m):
            if visited[i][j]==0 and graph[i][j]==1: # 방문 x, 그림 o
                queue=deque([[i,j]])
                visited[i][j]=1 
                dx=[-1,1,0,0] # 상하좌우
                dy=[0,0,-1,1]
                cnt=1 # 그림의 넓이
                while queue:
                    temp=queue.popleft()
                    for k in range(4):
                        x=temp[0]+dx[k]
                        y=temp[1]+dy[k]
                        if x>=0 and x<n and y>=0 and y<m: # 도화지 범위 안
                            if graph[x][y]==1 and visited[x][y]==0:
                                visited[x][y]=1
                                queue.append([x,y])
                                cnt+=1
                area.append(cnt) # 그림의 넓이 저장

    if len(area)==0: # 그림이 하나도 없는 경우
        print(0) 
        print(0)
    else:
        print(len(area)) # 그림의 개수
        print(max(area)) # 가장 넓은 그림의 넓이

 

- my solution (JAVA)

메모리 초과가 발생했다... 왜...?

 

 

그림이 그려져 있는 곳에서 상하좌우를 탐색하여 그림이 그려져 있다면 그 칸으로 이동하여 그림의 넓이를 구한다.

 

• 세로 크기 (n), 가로 크기 (m) 입력
• visited = 방문 여부
• area = 그림의 넓이 저장
• 그림의 정보 입력
• graph를 순환하여 아직 방문하지 않았으며 그림이 그려져 있다면 -> queue에 추가 및 방문 표시, cnt =1 -> queue가 빌 때까지 반복 -> 제일 처음 값을 pop -> 상하좌우로 이동하여 graph 범위 안이며 그림이 그려져 있고 아직 방문하지 않았다면 -> 방문 표시, queue에 추가, cnt +1 -> while문이 끝나면 그림의 넓이 저장
• 그림이 하나도 없는 경우 -> 0 출력
• 그림이 있는 경우 -> 그림의 개수, 가장 넓은 그림의 넓이 출력

 

❓ 처음에 런타임 에러가 발생한 이유는?

그림이 하나도 없는 경우를 고려하지 못했기 때문이다. 그래도 빨리 알아내서 해결할 수 있었다.

 

---

생각🤔

 

자바... 왜 메모리 초과인지 모르겠다.

---