태야

www.acmicpc.net/problem/2667

<내 코드>

from collections import deque


def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    cnt = 0
    queue = deque()

    queue.append((x, y))
    maps[x][y] = '0'
    done.append((x, y))

    while queue:
        now = queue.popleft()
        cnt += 1

        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if(0 <= nx < N) and (0 <= ny < N):
                if maps[nx][ny] == '1' and ((nx, ny) not in done):
                    maps[nx][ny] = '0'
                    queue.append((nx, ny))
                    done.append((nx, ny))
    return cnt


N = int(input())
maps = [list(input()) for _ in range(N)]
done = []
total = 0
result = []


for i in range(N):
    for j in range(N):
        if maps[i][j] == '1':
            result.append(bfs(i, j))
            total += 1

result.sort()
print(total)
for i in range(total):
    print(result[i])

크게 어려움 없이 BFS 알고리즘만 구현하면 쉽게 풀리는 문제였다. 각 BFS마다 total과 cnt 값을 올려줘 총 몇 번의 BFS 탐색을 했고, 각 탐색 중 몇 번의 인접한 요소들을 찾아냈는지 표시했다. 그리고 그 값들을 출력해주면 끝이다.

<내 코드>

from collections import deque


def bfs(x, y):
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1),
                 (1, 1), (1, -1), (-1, 1), (-1, -1)]

    queue = deque() #탐색을 하려는 좌표를 담는다.
    queue.append((x, y))

    maps[x][y] = 0

    while queue:
        now = queue.popleft()

        for i in range(8): #상하좌우 대각선까지 탐색
            nx = now[0] + direction[i][0]
            ny = now[1] + direction[i][1]

            if(0 <= nx < h) and (0 <= ny < w):
                if maps[nx][ny] == 1:
                    maps[nx][ny] = 0
                    queue.append((nx, ny))


while True:

    w, h = map(int, input().split())
    maps = []
    cnt = 0

    if w == 0 and h == 0:
        break

    for _ in range(h):
        tmp = list(map(int, input().split()))
        maps.append(tmp)

    for i in range(h):
        for j in range(w):
            if maps[i][j] != 0:
                cnt += 1
                bfs(i, j)

    print(cnt)

1. w, h, 지도를 입력받는다.

2. 매 입력마다 BFS 탐색을 마치면 cnt를 +1 해준다.

3. BFS를 상하좌우 그리고 대각선까지 여덟 방향을 다 탐색한다.

4. 탐색 중 지도에서 1인 값을 0으로 바꾸고 큐에 좌표를 넣고 탐색을 반복한다.

<내 코드>

N, M = map(int, input().split())
maze = [list(input()) for _ in range(N)]  # List[str]
# 방문 경로
done = [[0]*M for _ in range(N)]

# 좌,우,상,하 탐색을 위한 설정
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# BFS 그래프 탐색
def bfs(x, y):

    done[0][0] = 1  # 시작점
    queue = [(0, 0)]  # 큐 사용

    while queue:
        now = queue.pop(0)
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]

            if (0 <= nx < N) and (0 <= ny < M):
                if done[nx][ny] == 0 and maze[nx][ny] == '1':
                    done[nx][ny] = done[now[0]][now[1]] + 1
                    queue.append((nx, ny))
    return done[-1][-1]

print(bfs(0, 0))

처음 풀어보는 BFS 문제였는데.. 이해하는데 꽤나 어려웠다. 계속 반복적으로 생각하고 익혀야겠다.

1. 방문한 경로를 저장하기 위해 done 배열을 만든다.

2. 길을 찾아나갈 노드를 queue에 담아준다.

3. 좌표가 경로를 벗어나지 않는다면 '방문 여부 확인', '길이 맞는지' 확인한다.

4. 상,하,좌,우로 확인해 연결된 좌표를 확인한다.

5. 조건에 맞다면 방문 여부 수정 후, 큐에 넣어 다음 차례에 추가한다.

6. 방문여부 수정 때, 몇 번째 방문인지 현재 좌표의 방문 값에 +1을 더해준다.

7. done 배열의 가장 마지막 요소를 출력하면 몇 번째만에 도착인지 알 수 있다.