[알고리즘] 백준 11123 파이썬 - 양 한마리... 양 두마리...

 

11123번: 양 한마리... 양 두마리...

문제

얼마전에 나는 불면증에 시달렸지... 천장이 뚫어져라 뜬 눈으로 밤을 지새우곤 했었지.  그러던 어느 날 내 친구 광민이에게 나의 불면증에 대해 말했더니 이렇게 말하더군. "양이라도 세봐!"  정말 도움이 안되는 친구라고 생각했었지. 그런데 막상 또 다시 잠을 청해보려고 침대에 눕고 보니 양을 세고 있더군... 그런데 양을 세다보니 이걸로 프로그램을 하나 짜볼 수 있겠단 생각이 들더군 후후후... 그렇게 나는 침대에서 일어나 컴퓨터 앞으로 향했지.

양을 # 으로 나타내고 . 으로 풀을 표현하는 거야. 서로 다른 # 두 개 이상이 붙어있다면 한 무리의 양들이 있는거지. 그래... 좋았어..! 이걸로 초원에서 풀을 뜯고 있는 양들을 그리드로 표현해 보는거야!

그렇게 나는 양들을 그리드로 표현하고 나니까 갑자기 졸렵기 시작했어. 하지만 난 너무 궁금했지. 내가 표현한 그 그리드 위에 몇 개의 양무리가 있었는지! 그래서 나는 동이 트기 전까지 이 프로그램을 작성하고 장렬히 전사했지. 다음날 내가 잠에서 깨어났을 때 내 모니터에는 몇 개의 양무리가 있었는지 출력되어 있었지.

 

문제풀이

from collections import deque
t=int(input())

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

- #01 : bfs가 실행되었을 때 즉 #04번을 참고하면 graph[i][j]가 #일 때 실행된다.

          그 값을 "."로 바꿔주고 q에 추가해준다. dx와 dy라는 상하좌우로 움직일 수 있는

          좌표도 정의해준다.

- #02 : for문을 통해 0~3까지 dx,dy의 좌표를 바꾸어가며 graph[nx][ny]가 #인 값을 찾는다.

           #이라면 q에 추가해주고 값을 "."로 바꾸어준다.

           즉 인접한 값도 하나의 무리라고 간주하기에 따로 count하지는 않는다.

- #03 : graph를 입력한 값대로 만들어주고, for문을 통해 graph의 모든 값을 방문한다.

           만약 graph[i][j]가 #이라면 bfs를 실행해주고, 무리의 개수는 ans에 1을 더해준다.

           최종적으로 구한 ans를 출력하고, 다음 테스트로 넘어간다.