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 t = int(input()) for _ in range(t): m, n, k = map(int, sys.stdin.readline().rstrip().split()) board = [] visited = [] vegetable = [] worm_num = 0 dir = [[-1, 0], [0, 1], [1, 0], [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를 간단하게 작성할 수 있으니 익혀두어야 겠다.
Road to..