99클럽 코테 스터디 34일차 TIL + 백준 깊이너비탐색

오늘의 주제 : 깊이 너비 탐색문제

링크 : 백준 11123

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

n = int(input()) #테스트 케이스 수 n을 입력받음 아 그래서 2가 있었구나
ary = [] #각테스트케이스마다 mxk크기의 그리드를 입력받아 ary리스트에 저장함
mkary = [] #mkary리스트에는 각 그리드의 크기 (m,k)가 저장됨

for i in range(n): 
    m, k = map(int, input().split())
    mkary.append((m, k))
    tmpary = []
    for j in range(m):
        tmpary.append(list(map(str, input())))
    ary.append(tmpary)

def bfs(graph, x, y, xlen, ylen):
    q = deque()
    q.append((x,y))
    rslt = 1
    graph[x][y] = '.'

    while q:
        cx, cy = q.popleft()

        for m in range(len(dx)):
            nx = cx + dx[m]
            ny = cy + dy[m]

            if nx < 0 or nx >= xlen or ny < 0 or ny >= ylen:
                continue

            if ary[i][nx][ny] == '#':
                q.append((nx, ny))
                ary[i][nx][ny] = '.'
                rslt += 1

    return rslt
#bfs함수정의
#특정좌표 (x,y)에서 시작해서 연결된 모든 #를탐색 그리고 그 영역의 크기를 반환
#그래프[x][y]는 현재위치를 방문했음을 표시
#네방향으로 인접한 노드를 탐색해 #인경우 큐에 추가하고 탐색을 이어감
#반환값은 rslt 하나의 무리내의 양의 수를 나타냄

totalcnt = []
for i in range(n): ## n개 만큼의 양 그리드 확인
    cnt = []
    for j in range(mkary[i][0]):
        for x in range(mkary[i][1]):
            if ary[i][j][x] == '#':
                cnt.append(bfs(ary[i], j, x, mkary[i][0], mkary[i][1]))
    totalcnt.append(cnt)

for i in range(len(totalcnt)):
    print(len(totalcnt[i]))

# 각 테스트 케이스에 대해 양의 무리를 찾아 그 개수를 cnt 리스트에 저장
# 각 무리의 크기는 bfs 함수를 통해 계산되며, cnt 리스트에 추가됩니다.
# 마지막에 각 테스트 케이스마다 무리의 개수를 출력합니다(print(len(totalcnt[i]))).

 

안녕하세요 전 별가빠가사리에요

흑흑흑흑

저번이랑 똑같이 무슨유형인진 알겠는데

감을 0.000000000000000000000001퍼만 잡은상태

아 이번주 스택 무조건 마스터하고 

dfs/bfs넘어갑니다.