Jinho Tech

간단한 BFS 문제이다.

S에서 G로 가는 최단경로의 길이를 출력해주면 된다. 경로가 없다면 No Exit 출력

from collections import deque

def bfs(i, j):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((i, j))
    check[i][j] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != 'X' and check[Y][X] == -1:
                check[Y][X] = check[y][x] + 1
                if graph[Y][X] == 'G':
                    return check[Y][X]
                q.append((Y, X))
    return None

for _ in range(int(input())):
    R, C = map(int, input().split())
    graph = [input() for a in range(R)]
    check = [[-1]*C for b in range(R)]
    
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 'S':
                ans = bfs(i, j)
                print(f"Shortest Path: {ans}" if ans else "No Exit")

기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다.

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x, li[y][x]))
    while q:
        y, x, d = q.popleft()
        for i, j in [(1, 0), (0, 1)]:
            Y, X = y + d*i, x+ d*j
            if 0 <= Y < N and 0 <= X < N and d != 0:
                if Y == X == N-1:
                    return True
                q.append((Y, X, li[Y][X]))
    return False
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]    
print("HaruHaru" if bfs(0, 0) else "Hing")

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x):
    global ok
    d = li[y][x]
    for i, j in [(1, 0), (0, 1)]:
        Y, X = y + d*i, x+ d*j
        if 0 <= Y < N and 0 <= X < N and d != 0:
            if Y == X == N-1:
                ok = 1
                return ;
            dfs(Y, X)
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
ok = 0
dfs(0, 0)
print("HaruHaru" if ok else "Hing")

기본적인 그래프 탐색 문제이다. 

각 노드별로 몇 명의 사람을 만날 수 있는지 확인하고, 최댓값의 인덱스를 출력해주면 된다 -> res.index(max(res))

def dfs(node, cnt):
    check[node] = 1
    n = graph[node][0]
    if check[n] == 0:
        cnt = dfs(n, cnt+1)
    return cnt

N = int(input())
graph = [[] for _ in range(N+1)]
res = [0]*(N+1)
for u in range(1, N+1):
    v = int(input())
    graph[u].append(v)
for i in range(1, N+1):
    check = [0]*(N+1)
    res[i] = dfs(i, 1)
print(res.index(max(res)))

begin에서 target으로 가는 최단경로의 길이를 찾는 문제이다.

두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다.

if len([1 for i in range(N) if node[i] != n[i]]) != 1:

dfs를 사용해서 이동 가능한 모든 경로를 다 돌아보고 현재 node가 target이라면

res리스트에 지나왔던 경로의 길이를 append해준다. 마지막에 min(res)를 반환해주면 끝이다.

def solution(begin, target, words):
    def dfs(cnt, node, li, route):
        if node == target:
            res.append(cnt)
        for i, n in enumerate(li):
            if len([1 for i in range(N) if node[i] != n[i]]) != 1:
                continue
            li.pop(i)
            dfs(cnt+1, n, li, route+[n])
            li.insert(i, n)
            
    if target not in words:
        return 0
    
    N = len(begin)
    res = []
    dfs(0, begin, words, [begin])
    
    return min(res) if res else 0

기본적인 BFS 문제이다. 

B가 200점 이상이 되는 최단경로는 없을 것 같아서 check 리스트 크기를 200으로 정했다. 

from collections import deque

def bfs(S, T):
    q = deque()
    q.append((S, T, 0))
    check = [-1]*(200)
    while q:
        node, t, c = q.popleft()
        if node <= t and check[node] == -1:
            q.append((node*2, t+3, c+1))
            q.append((node+1, t, c+1))
            if node == t:
                return c

C = int(input())
for _ in range(C):
    S, T = map(int, input().split())
    print(bfs(S, T))

앞, 뒤 방향과 노드별 이동거리 모두 고려해줘야 되는 bfs 문제이다.

아래와 같이 앞, 뒤 방향의 경우로 둘로 나눠서 반복문을 짜면 96ms로 통과된다.

from collections import deque

def bfs(a, b, bridge, N):
    q = deque()
    q.append(a-1)
    check = [-1]*N
    check[a-1] = 0
    while q:
        node = q.popleft()
        for n in range(node, N, bridge[node]):
            if check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
        for n in range(node, -1, -bridge[node]):
            if check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
    return -1

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())
print(bfs(a, b, bridge, N))

단순하게 짧게 짜 봤는데도 976ms로 통과됐다.

from collections import deque

def bfs(a, b, bridge, N):
    q = deque()
    q.append(a-1)
    check = [-1]*N
    check[a-1] = 0
    while q:
        node = q.popleft()
        for n in range(N):
            if (n-node)%bridge[node] == 0 and check[n] == -1:
                q.append(n)
                check[n] = check[node] + 1
                if n == b-1:
                    return check[n]
    return -1

N = int(input())
bridge = list(map(int, input().split()))
a, b = map(int, input().split())
print(bfs(a, b, bridge, N))

골드 3 난이도 치고는 쉬운 다익스트라 알고리즘 문제이다.

N-1개(1->X->1, 2->X->2, ..., N->X->X (X->X->X 제외))의 최단경로 중 최댓값을 출력해주면 된다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start, end):
    q = []
    heapq.heappush(q, (0, start))
    dis = [INF]*(N+1)
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
    return dis[end]
    
N, M, X = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
t = 0
for i in range(1, N+1):
    if i == X:
        continue
    t = max(t, dijkstra(i, X) + dijkstra(X, i))
print(t)

기본적인 다익스트라 문제이긴 하다만, N-1번째 분기점을 제외하고 상대의 시야에 보이지 않는 분기점에만

방문해야 한다는 차이점이 있다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v] and check[v] == 0:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
check = list(map(int, input().split()))
check[-1] = 0
for _ in range(M):
    a, b, t = map(int, input().split())
    graph[a].append((b, t))
    graph[b].append((a, t))
dijkstra(0)
print(dis[N-1] if dis[N-1] != INF else -1)

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize
# input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
dis = [INF]*(n+1)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
s, t = map(int, input().split())
dijkstra(s)
print(dis[t])

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
dijkstra(1)
print(dis[N])

기본적인 플로이드-와샬 문제이다.

graph[a][k] == 1 and graph[k][b] == 1 이면 a에서 b로 갈 수 있다라는 점이 핵심이다.

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] and graph[k][b]:
                graph[a][b] = 1
for line in graph:
    print(*line)

기본적인 플로이드-와샬 문제이다. PyPy3로 제출해야 통과된다.

(특정 노드가 다른 노드를 가리키는 횟수 + 다른 노드가 특정 노드를 가리키는 횟수) == N-1이라면

그 특정 노드의 순서를 알 수 있다는 점이 핵심이다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[0]*N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
for k in range(N):
    for a in range(N):
        for b in range(N):
            if graph[a][k] == 1 and graph[k][b] == 1:
                graph[a][b] = 1
res = 0
for i in range(N):
    t = 0
    for j in range(N):
        t += graph[i][j] + graph[j][i]
    if t == N-1:
        res += 1
print(res)

기본적인 플로이드-와샬 문제이다. 

import sys
INF = sys.maxsize
input = sys.stdin.readline

n, m = int(input()), int(input())
dis = [[INF]*n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    if c < dis[a-1][b-1]:
        dis[a-1][b-1] = c
for k in range(n):
    for a in range(n):
        for b in range(n):
            if a != b:
                dis[a][b] = min(dis[a][b], dis[a][k]+dis[k][b])
for i in range(n):
    for j in range(n):
        if dis[i][j] == INF:
            dis[i][j] = 0
for t in dis:
    print(*t)

기본적인 다익스트라 문제이다.

import heapq
import sys
INF = sys.maxsize
input = sys.stdin.readline

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dis[start] = 0
    while q:
        d, now = heapq.heappop(q)
        if dis[now] < d:
            continue
        for v, w in graph[now]:
            cost = d + w
            if cost < dis[v]:
                dis[v] = cost
                heapq.heappush(q, (cost, v))
                
N, M = int(input()), int(input())
graph = [[] for _ in range(N+1)]
dis = [INF]*(N+1)
for _ in range(M):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
s, e = map(int, input().split())
dijkstra(s)
print(dis[e])

다익스트라 문제이긴 한데 조금 더 쉽게 풀 수 있는 문제이다. BFS랑 매우 비슷한 풀이다.

1. 최단거리 테이블 생성 -> [i for i in range(D+1)] = [0, 1, 2, 3, ... , D]

2. 한 칸 전 위치의 테이블 값+1이 현재 테이블 값보다 작다면 현재 테이블 값을 한 칸 전 위치의 테이블 값+1로 바꾼다. 

3. 현재 위치에 지름길이 있다면 지름길로 건너간 곳의 원래 테이블 값과 지름길로 건너가기 전의 테이블 값+지름길의 거리 중 더 작은 값으로 건너간 곳의 값을 바꾼다. 

N, D = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
dis = [i for i in range(D+1)]
for i in range(D+1):
    if i > 0:
        dis[i] = min(dis[i], dis[i-1]+1)
    for s, e, d in li:
        if i == s and e <= D and dis[i]+d < dis[e]:
            dis[e] = dis[i]+d
print(dis[D])