[파이썬] 백준 1926 : 그림 (실버1)

[파이썬] 백준 1926 : 그림 (실버1)

1926번: 그림

---

문제

---

풀이

0. 방향성 생각

• 영역 개수, 넓이 구하기

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[False]*w for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

2. BFS 함수 정의

def bfs(x,y):
    
    visit[y][x] = True
    q = deque([(x,y)])
    size = 1
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<w and 0<=ny<h and not visit[ny][nx] and arr[ny][nx] == 1:
                visit[ny][nx] = True
                q.append((nx,ny))
                size += 1
    return size

• size 계산해서 리턴해주기

3. 출력

info = []
for i in range(h):
    for j in range(w):
        if not visit[i][j] and arr[i][j] == 1:
            info.append(bfs(j,i))
if info:
    print(len(info))
    print(max(info))
else:
    print(0)
    print(0)

• 입력이 500 x 500이라 리스트에 넣는거보다 그냥 최댓값 갱신해주면서 푸는게 나았을듯

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(h)]
visit = [[False]*w for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

def bfs(x,y):
    
    visit[y][x] = True
    q = deque([(x,y)])
    size = 1
    while q:
        x,y = q.popleft()
        
        for dx,dy in dire:
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<w and 0<=ny<h and not visit[ny][nx] and arr[ny][nx] == 1:
                visit[ny][nx] = True
                q.append((nx,ny))
                size += 1
    return size

info = []
for i in range(h):
    for j in range(w):
        if not visit[i][j] and arr[i][j] == 1:
            info.append(bfs(j,i))
if info:
    print(len(info))
    print(max(info))
else:
    print(0)
    print(0)

 

코멘트

그림 없는 케이스 빼먹어서 잠깐 삽질함