백준 algorithm study 1916 2665 7569 다익스트라 bfs python

파이썬 알고리즘 : 최소비용 구하기, 미로 만들기, 토마토

백준 1916, 백준 2665, 백준 7569

2023년 8월 24일 알고리즘 문제풀이

문제1 백준 1916

문제 링크

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
33
34

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    s, a, c = map(int, sys.stdin.readline().split())
    graph[s][a] = c
start, arrive = map(int, sys.stdin.readline().split())


def search(x):
    cost = [10**9 for _ in range(n+1)]
    cost[x] = 0
    arr = []
    heappush(arr,[0, x])
    while arr:
        price, now = heappop(arr)
        if price > cost[now]:
            continue
        for i in range(1, n+1):
            if not graph[now][i]:
                continue
            new_money = price + graph[now][i]
            if new_money < cost[i]:
                cost[i] = new_money
                heappush(arr,[new_money, i])
    return cost


ans = search(start)
print(ans[arrive])

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
31
32
33

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    s, a, c = map(int, sys.stdin.readline().split())
    graph[s].append([c, a])
start, arrive = map(int, sys.stdin.readline().split())


def search(x):
    cost = [10**9 for _ in range(n+1)]
    cost[x] = 0
    arr = []
    heappush(arr, [0, x])
    while arr:
        price, now = heappop(arr)
        if price > cost[now]:
            continue
        for money, next in graph[now]:
            new_money = price + money
            if new_money < cost[next]:
                cost[next] = new_money
                heappush(arr, [new_money, next])
    return cost


ans = search(start)
print(ans[arrive])

문제 2 백준 2665

문제 링크

1차 시도

나의 생각

계속되는 다익스트라! 이번엔 다음 탐색할 곳이 검은색일때마다 이전보다 비용을 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
33
34
35
36
37
38
39
40
41
42

import sys
from heapq import heappop, heappush

n = int(sys.stdin.readline())
board = []
for _ in range(n):
    board.append(list(sys.stdin.readline().rstrip()))

da = [0, -1, 0, 1]
db = [1, 0, -1, 0]


def search(p, q):
    cnt = [[10**9 for _ in range(n)] for _ in range(n)]
    cnt[p][q] = 0
    arr = []
    heappush(arr, [0, p, q])
    while arr:
        cost, a, b = heappop(arr)
        for i in range(4):
            na = a + da[i]
            nb = b + db[i]
            if na < 0 or na > n-1 or nb < 0 or nb > n-1:
                continue
            if board[na][nb] == '0':
                new_value = cost + 1
            else:
                new_value = cost

            if cnt[na][nb] == 10**9:
                cnt[na][nb] = new_value
                heappush(arr, [new_value, na, nb])
            else:
                if new_value < cnt[na][nb]:
                    cnt[na][nb] = new_value
                    heappush(arr, [new_value, na, nb])
    return cnt

1
ans = search(0, 0)
print(ans[n-1][n-1])

문제 3 백준 7569

문제 링크

1차 시도

나의 생각

처음 모든 배열을 탐색하여 익은 토마토를 큐에 저장하였다. 그 후 동,서,남,북,상,하 6방향을 모두 탐색하여 익지 않은 토마토라면 익게 하고, 큐에 추가하도록 설정하였다. 문제는 비어있는 토마토 때문에 다 익은건지, 완성이 불가능한건지, 애초에 익어있는지에 대한 판단을 하는 로직을 세우는 것이 힘들었다..

결과

오답

코드

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
42
43
44
45
46
47
48
49
50
51

import sys
from collections import deque
m, n, h = map(int, sys.stdin.readline().split())
graph = []
for _ in range(h):
    tmp = []
    for _ in range(n):
        tmp.append(list(map(int, sys.stdin.readline().split())))
    graph.append(tmp)

da = [1, 0, -1, 0, 0, 0]
db = [0, 1, 0, -1, 0, 0]
dc = [0, 0, 0, 0, 1, -1]
tomato = deque()
cnt = 0
for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k] != -1:
                cnt += 1
            if graph[i][j][k] == 1:
                tomato.append((i, j, k, 0))
year = 0


def change(x):
    global year
    while tomato:
        c, b, a, y = tomato.popleft()
        print(b)
        for i in range(6):
            nc = c + dc[i]
            nb = b + db[i]
            na = a + db[i]
            if na < 0 or na >= m or nb < 0 or nb >= n or nc < 0 or nc >= h:
                continue
            else:
                if graph[nc][nb][na] == 0:
                    graph[nc][nb][na] = 1
                    tomato.append([nc, nb, na, y+1])
                    year = max(year, y+1)
                    x += 1
    return x


num = change(0)
if num == cnt:
    print(year)
else:
    print(-1)

2차 시도

나의 생각

익은 토마토와 안익은 토마토를 deque으로 관리하려고 했다. 효율성을 위해. 그런데 이 deque을 만드는 과정이 어차피 모든 그래프를 순환해야한다. 그래서 이미 수행시간을 아낄 수 없다고 생각해서 그냥 bfs로 싹다 바꾸고 결과가 어떤지 검색하는 함수를 만들었다. 그랬더니 정답! 괜히 어렵게 생각했다. 로직을 설명해보겠다.

기존에 행렬을 2차원 배열에 저장한 것을 3차원으로만 바꾼 것이다. 따라서 배열안에 배열안에 배열이 들어가는 것이다. 가로,세로,높이 중 어떤 index가 먼저 와야할지 헷갈릴 수 있다.

입력값을 봤을때 가장 먼저 따져야할 것을 찾으면 된다. 문제에도 나와있지만 H만큼 반복되서 입력된다고 하였다. 그래서 층을 먼저 따지게 된다. 층을 확정하고 나면 몇번째 줄인지를 따지게 된다. 줄은 n개까지. 문제의 그림상 세로를 의미한다. 마지막으로 m, 가로이다. 그림으로 보자면 입력된 것은

(1층,세1,가1) (1층,세1,가2) (1층,세1,가3)

(1층,세2,가1) (1층,세2,가2) (1층,세2,가3)

(2층,세1,가1) (2층,세1,가2) (2층,세1,가3)

(2층,세2,가1) (2층,세2,가2) (2층,세2,가3)

위와 같은 위치로 값이 입력된다. 따라서 3차원 배열에서 index는 층, 세로, 가로 순으로 찾아 들어가야한다. 아래 코드에서 a,b,c는 각각 가로, 세로, 높이를 나타내고 반복문에서 거꾸로 배정한 것도 그러한 이유이다.

3차원이라는 것을 제외하면 기존의 bfs와 동일하다. 동서남북을 따질때는 좌표의 이동이 4가지였지만 상과 하가 추가되었기에 6개가 되었다.

bfs를 수행한 후에 검사한다. bfs는 방문 가능한 모든 토마토를 거치고 나서야 종료된다. 이후 검사에서 안익은 토마토를 나타내는 0이 발견된다면? 모두 익을수 없다는 뜻이니까 -1을 나타낸다. 익은 토마토는 1로 표현되는데, 이 숫자를 통해 몇일이 지났는지를 표시했다. 처음부터 익은 것은 1, 1인 토마토로 인해 익은 것들은 하루 지나서 익었으니 2, 그다음 3 과 같은 규칙이었다. 모두 익은 날은 이 숫자에서 1을 빼서 알 수 있다.

숫자가 -1인 곳은 방문할 필요가 없고, 0인 곳은 방문을 아직 안했다는 의미이므로 굳이 방문처리를 위한 배열을 따로 만들지 않았다.

결과

정답

코드

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

import sys
from collections import deque
m, n, h = map(int, sys.stdin.readline().split())
graph = []
for _ in range(h):
    tmp = []
    for _ in range(n):
        tmp.append(list(map(int, sys.stdin.readline().split())))
    graph.append(tmp)

da = [1, 0, -1, 0, 0, 0]
db = [0, 1, 0, -1, 0, 0]
dc = [0, 0, 0, 0, 1, -1]
tomato = deque()
arr = []

for i in range(h):
    for j in range(n):
        for k in range(m):
            if graph[i][j][k] == 1:
                tomato.append([i, j, k])


def bfs():
    while tomato:
        c, b, a = tomato.popleft()

        for i in range(6):
            nc = c + dc[i]
            nb = b + db[i]
            na = a + da[i]
            if na < 0 or na >= m or nb < 0 or nb >= n or nc < 0 or nc >= h:
                continue
            if graph[nc][nb][na] == 0:
                graph[nc][nb][na] = graph[c][b][a] + 1
                tomato.append([nc, nb, na])


def answer(x):
    for i in range(h):
        for j in range(n):
            for k in range(m):
                if graph[i][j][k] == 0:
                    x = -1
                    return x
                if graph[i][j][k] > x:
                    x = graph[i][j][k]
    else:
        return x

bfs()
ans = answer(1)
if ans == -1:
    print(ans)
else:
    print(ans-1)
CATALOG
    algorithm