[알고리즘] 백준 14716 파이썬 - 현수막

 

14716번: 현수막

문제

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

 

문제풀이

from collections import deque
m,n=map(int,input().split())
graph=[]
for _ in range(m):
    graph.append(list(map(int,input().split())))
def bfs(x,y):
	#01
    q=deque([(x,y)])
    graph[x][y]=0
    dx=[-1,1,0,0,-1,-1,1,1]
    dy=[0,0,-1,1,-1,1,-1,1]
    while q:
        x,y=q.popleft()
        for i in range(8):
        	#02
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<m and 0<=ny<n and graph[nx][ny]==1:
                graph[nx][ny]=0
                q.append((nx,ny))
#03
ans=0
for i in range(m):
    for j in range(n):
        if graph[i][j]==1:
            bfs(i,j)
            ans+=1
print(ans)

- #01 : q에는 초기값을 (x,y)로 저장한다. 참고로 x,y는 bfs 실행 시 넘겨받은 인자값이다.

           dx,dy는 인접글자를 찾기 위한, 상하좌우 대각선 4곳을 포함한 총 8곳의 이동좌표이다.

- #02 : for문을 통해 dx와 dy의 값을 바꿔가며, 즉 상하좌우 대각선4곳을 모두 이동해보며,

           특정 조건을 만족하면 graph[nx][ny] 값을 0으로 바꾸고, q에 추가한다.

- #03 : ans 즉 답으로 출력할 변수는 0으로 지정해준다.

           i와 j를 통해 graph의 모든 경로를 하나하나 방문한다.

          만약 graph[i][j]가 1이라면 bfs를 통해 그 주변 인접 글자까지 모두 0으로 바꾸고,

          ans는 1만 추가해준다. (bfs에서 주변 1이 발견되어도 인접 글자로 1만 카운팅하기 때문이다.)

          이후 ans를 출력해준다.