[Python] 백준 1926 그림 - bfs알고리즘

참고 : https://www.youtube.com/watch?v=ansd5B27uJM 

 

 

 

예제 입출력

from collections import deque
import sys

input = sys.stdin.readline

# 세로, 가로
n,m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]

# 방문횟수 - 가로m개인 false리스트가 세로로 n개 있어야함
chk = [[False]*m for _ in range(n)]

# dy, dx는 그냥 외우기 - 좌표 이동에 사용됨
dy = [0,1,0,-1]
dx = [1,0,-1,0]

def bfs(y, x) :
    rs = 1
    q = deque()
    q.append((y,x))
    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if (0<=ny and ny<n) and (0<=nx and nx<m):
                if map[ny][nx] == 1 and chk[ny][nx] == False:
                    rs += 1
                    chk[ny][nx] = True
                    q.append((ny, nx))

    return rs


cnt = 0 # result
maxv = 0 # 가장 큰 지도
for j in range(n) :
    for i in range(m):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            cnt += 1
            maxv = max(maxv, bfs(j,i))
            # 전체 그림 갯수 +1
            # BFS > 그림 크기를 구해주고
            # 최대값 갱신

print(cnt)
print(maxv)

 

 

 

---

 

 

코드 분석!

 

- 큐 자료구조를 사용하므로  deque 선언

- sys 라이브러리로 input 시간을 간소화 시킬 것임

from collections import deque
import sys

 

 

- 세로, 가로를 입력받아주고 int 자료형으로 매핑시켜준다

- 입력 형태를 리스트 2중 리스트 구조로 만들어 줄 것 (컴프리헨션 작성법 잘 익혀두기!)

  - 한 행 입력받은것을 split해서 input으로 매핑시키고, 그 한 줄을 리스트로 저장하는데 이 동작을 n번 반복

* map의 형태 : [[1, 1, 0, 1, 1], [0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [1, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]

- chk도 이중 리스트구조이며, 방문체크를 위해 만든 리스트, 'False' 로 m개 채워진 리스트를 n개 만든다

# 세로, 가로
n,m = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(n)]

# 방문횟수 - 가로m개인 false리스트가 세로로 n개 있어야함
chk = [[False]*m for _ in range(n)]

 

 

- bfs 함수를 호출하는 main 부분

- cnt 는 그림의 개수, maxv는 지도의 최대 크기

- 이중포문은 보통 바깥 y, 내부 x포문으로 이루어져 있다 (바깥 세로, 내부 가로)

이중포문 진입

- map의 [j][i] 인덱스가 1이고(그림영역이고) chk의 [j][i] 인덱스가 False이면(방문하지 않았다면), 지도개수 +=1

- 이 때, 방문 체크

- bfs 알고리즘을 이용해 지도의 최대 크기도 구해보자.

cnt = 0 # result
maxv = 0 # 가장 큰 지도
for j in range(n) :
    for i in range(m):
        if map[j][i] == 1 and chk[j][i] == False:
            chk[j][i] = True
            cnt += 1
            maxv = max(maxv, bfs(j,i))
            # 전체 그림 갯수 +1
            # BFS > 그림 크기를 구해주고
            # 최대값 갱신

print(cnt)
print(maxv)

 

 

bfs 알고리즘 함수설명

- 좌표를 상,하,좌,우 이동하면서 체크해야 하기에 dy와 dx 선언과 그 용법은 암기해두는 것이 편하다

- q를 queue 자료구조로 선언해주고 매개변수 y,x를 저장해준다.

- y,x를 저장해주면서 while문이 살아있

# dy, dx는 그냥 외우기 - 좌표 이동에 사용됨
dy = [0,1,0,-1]
dx = [1,0,-1,0]

def bfs(y, x) :
    rs = 1
    q = deque()
    q.append((y,x))
    while q:
        ey, ex = q.popleft()
        for k in range(4):
            ny = ey + dy[k]
            nx = ex + dx[k]
            if (0<=ny and ny<n) and (0<=nx and nx<m):
                if map[ny][nx] == 1 and chk[ny][nx] == False:
                    rs += 1
                    chk[ny][nx] = True
                    q.append((ny, nx))

    return rs