[BOJ] 4485번: 녹색 옷 입은 애가 젤다지?

 

 

문제 링크

https://www.acmicpc.net/problem/4485

 

 

 

TIL

• 다익스트라 알고리즘
  • 최단 거리, 최소값 찾는 알고리즘이지만 "각 노드별 현재 최소값을 저장"하고 있다는 점이 특징
  • 현재 계산한 값이 기존 저장된 최소값보다 크거나 같다면 heappush 안함 (고려하지 않게 된다는 뜻)
    • 같아도 안됨. 무조건 더 작은 값만 !! 
    • 여기서 중요한 것은, 알고리즘이 '최단 경로의 길이'를 찾는 것이 목적이라면, 경로의 수나 경로 잔체는 중요하지 않음
    • 그러나, 모든 가능한 최단 경로를 기록하고자 한다면, 같은 길이의 경로도 갱신하고 저장해야 할 필요있음
  • 따라서 매 경로마다 최소값 비교를 하게 되고, 그 여부에 따라 push 여부가 결정되므로 visited check도 따로 안해도 됨
  •  
• 그래프의 여러 열 입력 받기 참고
  • grid = [list(map(int, input().split())) for _ in range(n)]
    • 이 방법 사용하기, append 없이 바로 삽입하면 됨 !!! 
  • append는 안에서 반복이 안됨, 하나의 요소만 받는 거 > extend 사용해야 함
    grid.append(list(map(int, input().split())) for _ in range(n))     >> 불가능
  • for i in range(n):
        grid.append(list(map(int, stdin.readline().split())))                >> 대신 이렇게 가능

 

 

[시간 초과 코드 -1]

import heapq

id = 0
while True:
    n = int(input())
    if n == 0:
        break
    
    id += 1
    grid = []
    # append는 안에서 반복이 안됨, 하나의 요소만 받는 거 > extend 사용해야 함
    #grid.append(list(map(int, input().split())) for _ in range(n))
    for i in range(n):
        grid.append(list(map(int, input().split())))

    directions = [(0,1), (1,0), (-1,0), (0,-1)]
    visited = [[False for _ in range(n)] for _ in range(n)]
    queue = [(grid[0][0], (0,0))]

    while queue:
        lost, (cy, cx) = heapq.heappop(queue)
        if cy==n-1 and cx == n-1:
            break
        
        visited[cy][cx] = True
        for dy, dx in directions:
            ny, nx = cy+dy, cx+dx
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
                heapq.heappush(queue, (lost+grid[ny][nx], (ny,nx)))

    print(f"Problem {id}: {lost}")

• 마지막 부분에서 최소값일때만 heappush를 하는 것이 아닌 모든 경우에 대해 push를 하기 때문에 시간 초과 발생

 

 

[시간 초과 코드 -2]

import heapq
from sys import stdin

id = 0
INF = int(1e9)
directions = [(0,1), (1,0), (-1,0), (0,-1)]

while True:
    n = int(input())
    if n == 0:
        break
    
    id += 1
    grid = [list(map(int, input().split())) for _ in range(n)]
    # append는 안에서 반복이 안됨, 하나의 요소만 받는 거 > extend 사용해야 함
    #grid.append(list(map(int, input().split())) for _ in range(n))
    # for i in range(n):
    #     grid.append(list(map(int, stdin.readline().split())))
        

    visited = [[False for _ in range(n)] for _ in range(n)]
    cost = [[INF] * n for _ in range(n)]
    queue = [(grid[0][0], (0,0))]

    while queue:
        lost, (cy, cx) = heapq.heappop(queue)
        if cy==n-1 and cx == n-1:
            break

        visited[cy][cx] = True
        for dy, dx in directions:
            ny, nx = cy+dy, cx+dx
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
                nlost = lost + grid[ny][nx]
                if nlost <= cost[ny][nx]:
                    cost[ny][nx] = nlost
                    heapq.heappush(queue, (nlost, (ny,nx)))

    print(f"Problem {id}: {lost}")

• if nlost <= cost[ny][nx] 때문에 시간 초과 발생

 

Code

import heapq

id = 0
INF = int(1e9)
directions = [(0,1), (1,0), (-1,0), (0,-1)]

while True:
    n = int(input())
    if n == 0:
        break
    
    id += 1
    grid = [list(map(int, input().split())) for _ in range(n)]

    visited = [[False for _ in range(n)] for _ in range(n)]
    cost = [[INF] * n for _ in range(n)]
    queue = [(grid[0][0], (0,0))]

    while queue:
        lost, (cy, cx) = heapq.heappop(queue)
        if cy==n-1 and cx == n-1:
            break

        visited[cy][cx] = True
        for dy, dx in directions:
            ny, nx = cy+dy, cx+dx
            if 0<=ny<n and 0<=nx<n and not visited[ny][nx]:
                nlost = lost + grid[ny][nx]
                if nlost < cost[ny][nx]:
                    cost[ny][nx] = nlost
                    heapq.heappush(queue, (nlost, (ny,nx)))

    print(f"Problem {id}: {lost}")

• visited check 안해도 됨 !!!!!!!!! > 다익스트라의 경우, 최소 거리를 노드마다 저장하고 있기에 그걸로 판별 가능
  • 애초에 현재 최소값보다 작아야지만 push를 하기 때문에, 그걸로 방문 여부를 대체해서 체크 가능
• 더 작은 값일때만 고려 !!!!! (크거나 같으면 애초에 고려 안함)