BJ_ 14719 그림

문제 링크

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

1926번: 그림

 

1062 가르침, 2668 숫자고르기에 먼저 도전했지만, 비트마스킹과 유향가중그래프라는 벽에 막혀 문제를 풀지 못하였다

담주에는 꼭 둘 중 하나를 풀어서 포스팅하겠다

---

문제  설명/ 풀이

이차원 배열로 그림의 모양을 받고,

처음부터 돌면서 1인 지점을 발견하면 n으로 바꿔주며 bfs를 수행한다

bfs를 모두 수행하면 그림의 숫자를 n+1로 바꿔주고

이차원 배열을 모두 탐색한다.

모두 탐색한 후 Counter로 그림의 종류와 숫자를 세준다

---

코드

import sys
from collections import deque
from collections import Counter
n, m = map(int,sys.stdin.readline().split())

l = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n)] # 지도 그리기

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
level = 2 # 그림 번호

# 맵을 돌면서
for i in range(n):
    for j in range(m):
        if l[i][j] == 1:
            l[i][j] = level
            q = deque()
            q.append((i, j))
            while q:
                y, x = q.popleft()
                for r in range(4):
                    nx = x + dx[r]
                    ny = y + dy[r]
                    if 0 <= nx < m and 0 <= ny < n and l[ny][nx] == 1:
                        l[ny][nx] = level # 그림 라벨링
                        q.append((ny, nx))
            level += 1 # 그림 라벨링이 끝나면 그림번호 +1

# Counter로 단지 개수 세기
C = Counter([])
for i in range(n):
    C += Counter(l[i])

# 0번 단지가 있다면
if(0 in C):
    C.pop(0) # 0번 단지는 아파트가 없는곳이므로 삭제
print(len(C)) # 그림 개수 출력

# 그림이 있으면 가장 넓은 그림 넓이 출력
if C:
    # Counter에는 sort가 없어서 리스트로 만들어서 정렬 출력
    tmp = []
    for i in C.values():
        tmp.append(i)

    print(sorted(tmp, reverse = True)[0])

# 그림이 없으면 0출력
else:
    print(0)

Counter를 쓰지말고 bfs를 돌면서 그림의 개수와 최대넓이를 세주었으면 좀 더 공간 복잡도를 줄일 수 있었을 것 같다