참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

실전 문제 1 - 음료수 얼려먹기

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
from collections import deque

n, m = map(int, input().split())

graph = []

for i in range(n):
    graph.append([int(x) for x in list(input())])

visited = [[False] * m for _ in range(n)]
count = 0
steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for i in range(n):
    for j in range(m):
        # bfs
        if graph[i][j] == 0 and visited[i][j] == False:
            count += 1
            queue = deque([(i, j)])
            while queue:
                y, x = queue.popleft()
                visited[y][x] = True
                for step in steps:
                    ny, nx = y + step[0], x + step[1]
                    if ny < 0 or ny >= n or nx < 0 or nx >= m:
                        continue
                    elif graph[ny][nx] == 1 or visited[ny][nx]:
                        continue
                    else:
                        queue.append((ny, nx))

print(count)

BFS로 해결함

실전 문제 2 - 미로 탈출

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
from collections import deque

n, m = map(int, input().split())

graph = []

for i in range(n):
    graph.append([int(x) for x in list(input())])

visited = [[False] * m for _ in range(n)]
steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]

queue = deque([(0, 0, 1)]) # y, x, depth

while queue:
    y, x, d = queue.popleft()
    visited[y][x] = True

    if y == n - 1 and x == m - 1:
        print(d)
        break

    for step in steps:
        ny, nx = y + step[0], x + step[1]
        if ny < 0 or ny >= n or nx < 0 or nx >= m:
            continue
        elif visited[ny][nx] or graph[ny][nx] == 0:
            continue
        else:
            queue.append((ny, nx, d + 1))