[백준] 1753, 1654, 1012, 2206

최단경로 (1753번)

• 사이트/난이도: 백준 / 골드4
• 코드

# 골드4 최단경로
import sys
import heapq
input = sys.stdin.readline

v, e = map(int, input().split())
k = int(input())

INF = int(1e9)
distance = [INF] * (v+1)
graph = [[] for _ in range(v+1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b,c))

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]:
            cost = dist + i[1]
            if distance[i[0]] > cost:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(k)
for i in range(1, v+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

• 느낀점
  • 다익스트라 알고리즘 문제
  • 정점과 간선개수가 2만, 30만이므로 시간복잡도가 $O(ElogV)$ (E: 간선, V: 노드) 인 우선순위 큐를 이용하는 다익스트라 알고리즘을 사용해야된다.
  • 다익스트라 알고리즘
    • 특정한 노드에서 다른 모든 노드로 가는 최단 경로
    • 음의 간선이 없을 때 정상 동작
    • 매 상황에서 가장 비용이 적은 노드 선택 (그리디 알고리즘으로 분류)
    • 동작 과정
      1. 출발 노드 설정
      2. 최단 거리 테이블 초기화 (무한으로)
      3. 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드 선택
      4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
      5. 3, 4번 반복

랜선 자르기 (1654번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 랜선 자르기
import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lengths = []
for _ in range(k):
    lengths.append(int(input()))

def get_count(mid):
    count = 0
    for l in lengths:
        count += l // mid
    return count

def binary_search(start, end):
    while start <= end:
        mid = (start + end) // 2
        print(start, end, mid)
        result = get_count(mid)
        if result >= n: # 자른 개수가 더 많으면 -> 크게 잘라야함
            start = mid + 1
        else:
            end = mid - 1
    return end

print(binary_search(1, max(lengths)))

• 느낀점
  • 랜선의 길이와 n, k범위가 엄청 크므로 logN의 시간복잡도를 가지는 이진탐색을 이용해야한다.
  • 여기서 헤멨던게 최대 랜선 길이를 가져야 하므로 해당 랜선 개수를 만족하는 mid를 가지고 끝내는게 아닌 해당 랜선 개수 이상일 때 계속 반복하면서 최대 길이인 end를 반환해야 한다.
  • 아래 블로그에서 자세하게 설명해준다.
  • https://velog.io/@ledcost/백준-1654-파이썬-랜선-자르기-실버3-이분-탐색

유기농 배추 (1012번)

• 사이트/난이도: 백준/실버2
• 코드

# 실버2 유기농 배추
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == 1:
                graph[nx][ny] = -1
                dfs(nx,ny)

t = int(input())
for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        graph[x][y] = 1

    answer = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(i, j)
                answer += 1
    print(answer)

• 느낀점
  • 기본적인 dfs 문제
  • 최대 재귀 한도인 sys.setrecursionlimit(10000) 을 처음에 설정 안해서 런타임에러로 실패했음

벽 부수고 이동하기 (2206번)

• 사이트/난이도: 백준/골드4
• 코드

# 골드4 벽 부수고 이동하기
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
# 3차원 행렬 visited[x][y][z] => z = 0 이라면 벽 파괴 가능 / z = 1 이라면 벽 한번 뚫은 상태
# 중간에 벽을 부순 경로는 벽을 안부순 경로만 이동 가능, 벽을 안부순 경로는 그 이후 벽을 한번 부술 경로로 이동 가능
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs():
    q = deque([])
    q.append((0, 0, 0))
    visited[0][0][0] = 1

    while q:
        x, y, z = q.popleft()
        if x == n-1 and y == m-1:
            return visited[x][y][z]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and visited[nx][ny][z] == 0: # 벽이 아니고 한번도 방문 안했다면
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    q.append((nx, ny, z))
                elif graph[nx][ny] == 1 and z == 0: # 벽이고 아직 벽 파괴를 사용하지 않았다면
                    visited[nx][ny][1] = visited[x][y][z] + 1
                    q.appendleft((nx, ny, 1))
    return -1
print(bfs())

• 느낀점
  • 기본적인 bfs + 벽 부수는 응용 문제
  • 벽 부수는 것을 visited에 3차원 배열로 해서 표시해준다.
  • 처음에 접근할 떄는 그냥 큐에다가 부쉈는지 안부쉈는지를 표시해주는 변수 하나만 더 추가해줬는데 이렇게 해서 graph에다가만 방문표시 해주면 임의의 x,y 좌표에서 벽 부수고 온 경로와 벽 안부수고 온 경로가 혼합되어 오류가 난다..
  • 그러므로 3차원 배열로 벽 안부수고 온 경로는 이후에 벽을 부술수 있는 경로로 이동할 수 있게 하고, 벽을 부수고 온 경로는 벽 안부수는 경로로만 가게하여 최단거리를 구한다.
  • 아래 블로그를 참고했다.
  • https://hongcoding.tistory.com/18