백준 알고리즘) 그래프 문제 풀이

[18352] 특정 거리의 도시 찾기

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e9))

def dfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    global distance
    distance = max(distance, len(alpa))
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx<R and 0<=ny<C:
            if graph[nx][ny] not in alpa:
                alpa.add(graph[nx][ny])
                dfs(nx, ny)
                alpa.remove(graph[nx][ny])  # 백트래킹
            
R, C = map(int, input().split())
graph = []
for _ in range(R):
    graph.append(list(input().rstrip()))

distance = 0
alpa = set()
alpa.add(graph[0][0])

dfs(0,0)
print(distance)

 

다익스트라 알고리즘을 이용해 풀이했다. 

---

[1987] 알파벳

Python3 (시간초과) 오답, PyPy3 정답

Python3로 제출하면 시간초과가 떠서 setrecursionlimit을 걸어줬다.

하지만 그래도 시간초과,,, 검색을 해보니 PyPy3로 제출하면 정답이 나오는 경우도 있다고 해서

제출했는데 이번엔 메모리 초과가 떴다. 또 찾아보니 sys 관련 코드를 지우면 정답이 나온대서

sys 관련 코드를 지우고 제출했더니 정답이 나왔다.

 

이건 무슨 경우인가...!

# import sys
# input = sys.stdin.readline
# sys.setrecursionlimit(int(1e9))

def dfs(x, y):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    global distance
    distance = max(distance, len(alpa))
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0<=nx<R and 0<=ny<C:
            if graph[nx][ny] not in alpa:
                alpa.add(graph[nx][ny])
                dfs(nx, ny)
                alpa.remove(graph[nx][ny])  # 백트래킹
            
R, C = map(int, input().split())
graph = []
for _ in range(R):
    graph.append(list(input().rstrip()))

distance = 0
alpa = set()
alpa.add(graph[0][0])

dfs(0,0)
print(distance)

---

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

import sys
input = sys.stdin.readline
import heapq

def dijkstra(x, y):
    q = []
    heapq.heappush(q, (graph[x][y], x, y))
    distance[x][y] = graph[x][y]
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while q:
        dist, x, y = heapq.heappop(q)
        
        if distance[x][y]<dist:
            continue
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<N and 0<=ny<N:
                cost = dist + graph[nx][ny]

                if distance[nx][ny]>cost:
                    distance[nx][ny] = cost
                    heapq.heappush(q, (cost, nx, ny))
index = 0    
while True:
    N = int(input())
    index += 1
    if N==0:
        break

    graph = []
    INF = int(1e9)
    distance = [[INF]*N for _ in range(N)]
    
    for _ in range(N):
        graph.append(list(map(int, input().split())))
    
    dijkstra(0,0)
    print(f'Problem {index}: {distance[N-1][N-1]}')

각 칸의 숫자가 적은 곳으로 이동해야 잃는 금액을 최소화할 수 있다.

최단경로 알고리즘인 다익스트라 알고리즘을 활용해 문제를 풀었다.