BOJ 4993_Red and Black : BFS알고리즘 - 파이썬

문제

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

입력

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

• '.' - a black tile
• '#' - a red tile
• '@' - a man on a black tile(appears exactly once in a data set)

The end of the input is indicated by a line consisting of two zeros.

출력

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

 

제출코드

from collections import deque

# 이동할 네가지 방향 정의 (상하좌우)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def bfs(x, y):
    queue = deque()
    queue.append((a, b))
    graph[x][y] = 0  # 방문처리
    count = 1
    while queue:
        x, y = queue.popleft()

        for i in range(4):  # 4가지 방향으로 위치확인
            nx = x + dx[i]
            ny = y + dy[i]

            # 위치가 벗어나면 안되기 때문에 조건 추가
            if nx < 0 or nx >= H or ny < 0 or ny >= W:
                continue

            # 빨강타일이므로 진행 불가
            if graph[nx][ny] == "#":
                continue

            # 검정타일이므로 이동
            if graph[nx][ny] == ".":
                queue.append((nx, ny))
                graph[nx][ny] = 0
                count += 1

    return count

while True:
    W, H = map(int, input().split())
    graph = []

    if W == 0 and H == 0:
        break

    for _ in range(H):
        graph.append(list(map(str, input())))

    for a in range(H):
        for b in range(W):
            if graph[a][b] == "@":
                count = bfs(a, b)

    print(count)