백준 파이썬 1012번

7521 단어 pythonBFS백준BFS

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

BFS(깊이 우선 탐색)을 이론적으로 배우기만 하고 구현을 해보진 않았는데 이 문제로 연습을 해보았다.

생각해본 풀이방법

1. 농장을 나타내는 board와 visited list를 만든다.

2. 배추의 위치를 입력받을 때 그 좌표를 받는 list를 만든다.

3. 이후 배추 좌표 list를 반복문으로 꺼내서 BFS를 진행한다.

4. BFS를 통해 어떤 배추 좌표의 인접한 모든 배추 좌표가 visited되므로 BFS 작업을 한 번 끝낼때마다 지렁이 개수를 1개 추가한다.

* 과정 3이 진행되는 동안 방문된 배추 좌표는 BFS를 진행하지 않는다

이를 통해 모든 좌표를 검사하는 불필요한 작업을 피할 수 있다.
이 작업을 위해 농장을 나타내는 board list와 visited list도 작성했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import sys
 
= int(input())
for _ in range(t):
    m, n, k = map(int, sys.stdin.readline().rstrip().split())
    board = []
    visited = []
    vegetable = []
    worm_num = 0
    dir = [[-10], [01], [10], [0-1]]
    # Make farm and visit record
    for _ in range(m):
        board.append([0* n)
        visited.append([0* n)
    # Put vegetables
    for _ in range(k):
        x, y = map(int, sys.stdin.readline().rstrip().split())
        vegetable.append([x, y])
        board[x][y] = 1
    # Execute BFS
    for i, j in vegetable:
        # if visited vegetable, pass
        if visited[i][j] == 1:
            continue
        # start BFS
        visited[i][j] = 1
        queue = []
        queue.append([i, j])
        while queue:
            cur_x, cur_y = queue.pop()
            for jumpx, jumpy in dir:
                next_x = cur_x + jumpx
                next_y = cur_y + jumpy
                if next_x < 0 or next_x >= m or next_y < 0 or next_y >= n:
                    continue
                if board[next_x][next_y] == 1 and visited[next_x][next_y] != 1:
                    visited[next_x][next_y] = 1
                    queue.append([next_x, next_y])
        worm_num += 1
    print(worm_num)
 
cs

그래프 생성

graph = [[0] * n for _ in range(m)]

이렇게 그래프를 나타내는 list를 간단하게 작성할 수 있으니 익혀두어야 겠다.

좋은 웹페이지 즐겨찾기