리스트 복사할 때 deepcopy 대신 slicing을 사용하자

deepcopy보다 slicing이 훨씬 빠르다

# 1차원 리스트 복사
a= [1, 2, 3]
b = arr[:]

# 2차원 리스트 복사
a = [[1, 2], [3, 4]]
b = [item[:] for item in a]

그래프

골드4. 백준 1753 최단경로

풀이

정점과 정점 사이의 간선이 여러개일 수 있어 한번 더 처리해줘야 하는 문제이다. 시작 정점(K)이 주어지므로 다익스트라 알고리즘을 사용하면 된다.

최대 정점의 개수가 많아 매번 정점을 다 훑으면서 최소 거리 간선만 저장하는 것은 비효율적이어 딕셔너리를 사용했다.

만약 딕셔너리에 (시작정점, 도착정점) 값이 존재한다면 그 값과 입력받은 간선 값 중 작은 것을 저장한다. get 메서드를 사용하여 만약 한번도 입력받은 적이 없다면 int(1e9)를 기본값으로 불러오게 설정했다.

딕셔너리에 모든 입력값을 다 저장했다면 그래프에 값을 넣어준다. 이제 일반적인 다익스트라 방식으로 풀면 된다.

그래프[시작노드]에는 (도착노드, 가중치)가 담겨있으며, 최단거리 배열은 모두 int(1e9)로 초기화한다.

시작 노드의 거리값은 0으로 계산하며, 최단거리를 갖는 노드를 효율적으로 뽑아내기 위해 heapq를 사용한다. 힙에 (거리, 노드) 값을 넣고 만약 최단거리 배열[노드] 값보다 거리가 길다면 볼 필요 없으니 패스한다. 거리가 짧다면 연결된 노드를 모두 살펴보며 해당 노드로 가는 것이 더 유리한 경우 최단거리 배열을 업데이트하고 힙에 값을 넣어준다.

코드

from sys import stdin
import heapq

input = stdin.readline

V, E = map(int, input().split(" "))

# 시작정점의 번호
K = int(input())

# 그래프
graph = [[] for _ in range(V + 1)]

mydict = {}
for _ in range(E):
    u, v, w = map(int, input().split(" "))
    # 간선이 여러개일 수 있으니 최솟값만 저장하기
    mydict[(u, v)] = min(mydict.get((u, v), int(1e9)), w)

for key in mydict:
    s, e = key
    graph[s].append((e, mydict[key]))


# 최단거리 테이블
distance = [int(1e9) for _ in range(V + 1)]


# 다익스트라
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # (비용, 노드)로 힙에 값 넣기
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        # 최단거리 테이블을 살펴봤더니
        # 지금 길이가 더 길어서 살펴볼 필요가 없는 경우는 패스
        if distance[now] < dist:
            continue

        # 연결된 노드 살펴보기
        for i in graph[now]:
            next_node, next_node_dist = i
            cost = dist + next_node_dist
            if cost < distance[next_node]:
                distance[next_node] = cost
                heapq.heappush(q, (cost, next_node))


dijkstra(K)

for i in range(1, V + 1):
    if distance[i] == int(1e9):
        print("INF")
    else:
        print(distance[i])

골드5. 백준 10026 적록색약

풀이

BFS를 돌릴때 경우에 따라 방문해야되는 노드가 다르다.
만약 적록색약이 있는 경우, R, G를 같은 영역으로 체크한다. 따라서 BFS를 버전별로 다 만들어주었다.
R, G, B, R/G 를 체크할 수 있는 BFS 함수를 만들어 풀었다.

방문처리는 visit 배열을 만들어서 처리해주었다.

코드

from sys import stdin
from collections import deque

input = stdin.readline
N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]


dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]


def blue_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "B" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def red_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "R" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def green_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if graph[nr][nc] == "G" and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


def red_green_bfs(sr, sc, visit):
    q = deque([(sr, sc)])
    visit[sr][sc] = True
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if (graph[nr][nc] == "R" or graph[nr][nc] == "G") and not visit[nr][nc]:
                    visit[nr][nc] = True
                    q.append((nr, nc))


# 적록색약 X
count = 0
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
    for c in range(N):
        if not visit[r][c]:
            if graph[r][c] == "B":
                blue_bfs(r, c, visit)
            elif graph[r][c] == "R":
                red_bfs(r, c, visit)
            else:
                green_bfs(r, c, visit)
            count += 1

print(count, end=" ")

# 적록색약 O
count = 0
visit = [[False for _ in range(N)] for _ in range(N)]
for r in range(N):
    for c in range(N):
        if not visit[r][c]:
            if graph[r][c] == "B":
                blue_bfs(r, c, visit)
            else:
                red_green_bfs(r, c, visit)
            count += 1
print(count, end="")

골드5. 백준 7569 토마토

풀이

3차원 그래프에서 BFS를 돌려주면 된다. 2차원과 크게 차이는 없다. 살펴봐야하는 인덱스가 하나 더 늘어났을 뿐이다.

토마토가 여러군데에 있을 수 있다는 것에 주의하자! 즉, 시작하는 좌표(토마토 위치)를 싹 다 deque에 넣고 bfs를 돌려주면 된다.

저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고,
: 시작하는 좌표의 길이가 3차원 배열의 크기와 같은 경우

토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
: bfs를 돌리고 나서 graph에 0이 존재하는 경우

토마토가 익는데 걸리는 최소 날짜
: graph 내의 가장 큰 숫자 - 1

왜? : 방문처리 연산을 graph[좌표]+1로 해줬기 때문에 (시작하는 토마토의 값이 1이라서) 하루 빼줘야한다

골드로 넘어오면 확실히 고려할 것이 이것저것 생기는 느낌. 얼른 골드도 안전하게 1시간 안에 다 풀고싶다 ㅠ

코드

from sys import stdin
from collections import deque

input = stdin.readline
# M : col, N : row, H : height
M, N, H = map(int, input().split(" "))

graph = []
tomato = deque([])
for h in range(H):
    temp = []
    for r in range(N):
        data = list(map(int, input().split(" ")))
        for c in range(M):
            if data[c] == 1:
                tomato.append((h, r, c))
        temp.append(data)
    graph.append(temp)

# 6가지 방향 고려
# 3차원 기준 상하, 2차원 기준 상하좌우
dir_ = [[1, 0, 0], [-1, 0, 0], [0, -1, 0], [0, 1, 0], [0, 0, 1], [0, 0, -1]]


def bfs():
    while tomato:
        h, r, c = tomato.popleft()
        for i in range(len(dir_)):
            nh = h + dir_[i][0]
            nr = r + dir_[i][1]
            nc = c + dir_[i][2]

            if 0 <= nh < H and 0 <= nr < N and 0 <= nc < M:
                # 빈 칸
                if graph[nh][nr][nc] == -1:
                    continue
                # 안 익은 토마토
                if graph[nh][nr][nc] == 0:
                    graph[nh][nr][nc] = graph[h][r][c] + 1
                    tomato.append((nh, nr, nc))


# 모든 토마토가 익어있는 상태
if len(tomato) == H * M * N:
    print(0)

else:
    bfs()

    # 만약 0이 한개라도 존재한다면 -1 출력
    # 아니면 가장 큰 값-1 출력
    max_date = -int(1e9)
    for h in range(H):
        for r in range(N):
            for c in range(M):
                if graph[h][r][c] == 0:
                    print(-1)
                    exit(0)
                max_date = max(max_date, graph[h][r][c])

    print(max_date - 1)