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로 풀었다.

from collections import deque

def bfs():
    q = deque()
    q.append((0))
    while q:
        node = q.popleft()
        n = li[node]
        if check[n] == 0 and node != n:
            q.append(n)
            check[n] = check[node] + 1
            if n == K:
                return ;
    
N, K = map(int, input().split())
li = [int(input()) for _ in range(N)]
check = [0]*N
bfs()
print(check[K] if check[K] else -1)

기본적인 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

간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고

그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다.

check[i] = 0 -> i 노드 들린 적 없음 -> 탐색 시작

check[i] = 1 -> i 노드 들린 적 있음 -> 탐색 X 

보아하니 백준 실버 4 ~ 실버 2 정도가 프로그래머스 Level 3이랑 비슷한 것 같다.

DFS 풀이

def solution(n, computers):
    def dfs(node):
        if graph[node] and check[node] == 0:
            check[node] = 1
            for n in graph[node]:
                dfs(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            dfs(i)
            ans += 1

    return ans

BFS 풀이

from collections import deque

def solution(n, computers):
    def bfs(node):
        q = deque([node])
        while q:
            node = q.popleft()
            if graph[node] and check[node] == 0:
                check[node] = 1
                for n in graph[node]:
                    q.append(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            bfs(i)
            ans += 1

    return ans

리스트가 아닌 딕셔너리로 그래프를 구현해서 풀어야되는 문제이다.

올바른 경로를 찾을 때까지 뺑뺑이를 돌려줘야 되는 문제라 dfs로 풀었다. 

핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의 value값을 삭제하고 재귀후에 다시 추가해주는 부분같다.

처음에 이 부분을 잘못 생각해서 푸는데 오래걸렸다... 

from collections import defaultdict

def dfs(N, graph, route, node):
    if len(route) == N+1:
        return route
    for i, n in enumerate(graph[node]):
        graph[node].pop(i)
        ret = dfs(N, graph, route+[n], n)
        graph[node].insert(i, n)
        if ret:
            return ret
        
def solution(tickets):
    N = len(tickets)
    graph = defaultdict(list)
    for s, e in tickets:
        graph[s].append(e)
    for k in graph:
        graph[k].sort()
    
    route = dfs(N, graph, ["ICN"], "ICN") 
    return route

추가로 defaultdict라는 친구에 대해 알게되었다.

여태까지 딕셔너리에 값을 채울 때나 키값이 있는지 조건문으로 확인할 때 get을 사용해서 따로 처리하곤

했었는데, defaultdict를 사용하면 오류 걱정없이 그냥 넣어주고 확인하면 된다! 

순위를 정확하게 매길 수 있는 사람이 몇 명인지 찾는 문제이다.

플로이드 와샬 알고리즘을 모른다면 풀기 조금 힘들 것 같은 문제이다. 

플로이드 와샬을 사용해서 최단경로가 아닌 승패를 확인해주면 된다.  

EX)

graph[0][1] = 1 -> 1가 2를 이김

graph[4][3] = -1 -> 4가 5를 이김

graph[1][2] = 0 -> 2와 3의 승패를 알 수 없음 

def solution(n, results):
    graph = [[0]*n for i in range(n)]
    for a, b in results:
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = -1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] == 1 and graph[k][j] == 1:
                    graph[i][j] = 1
                if graph[i][k] == -1 and graph[k][j] == -1:
                    graph[i][j] = -1
    
    ans = 0
    for li in graph:
        if li.count(0) == 1:
            ans += 1
    return ans

1번 노드에서 제일 먼 노드가 몇 개 인지 찾는 문제이다. 

BFS로 아주 쉽게 풀 수 있다.

from collections import deque

def solution(N, edge):
    graph = [[] for _ in range(N+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    q = deque([1])
    check_li = [-1]*(N+1)
    check_li[1] = 0
    while q:
        node = q.popleft()
        for n in graph[node]:
            if 0 < n <= N and check_li[n] == -1:
                q.append(n)
                check_li[n] = check_li[node] + 1
                    
    ans = check_li.count(max(check_li))
    return ans

기본적인 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))

기본적인 플로이드-와샬 문제이다. 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)

너비 우선 탐색 or 다익스트라 문제인데 그냥 너비 우선 탐색으로 풀었다. 이전 숨바꼭질 문제와는 다르게 

순간이동할 때 걸리는 시간이 0이다. 이 점 때문에 node-1, node+1보다 node*2를 먼저 탐색을 해줘야 한다.

node*2를 node+1 보다 나중에 탐색해버리면 시작 노드가 1일 때 노드 2의 값이 0이 아닌 1이 되어버려서 틀린다.

from collections import deque

def bfs(N, K):
    queue = deque([N])
    graph[N] = 0
    while queue:
        node = queue.popleft()
        if node == K:
            return ;
        for n in [node*2, node-1, node+1]:
            if (0 <= n <= 100000) and graph[n] == -1:
                queue.append(n)
                graph[n] = graph[node] + (0 if n == node*2 else 1)
            
N, K = map(int, input().split())
graph = [-1]*100001
bfs(N, K)
print(graph[K])

다이나믹 프로그래밍 or 그래프 탐색 문제이다.

다이나믹 프로그래밍 풀이

N = int(input())
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]
for i in range(2, N+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    if i%2 == 0 and dp[i//2][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]
    if i%3 == 0 and dp[i//3][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]
print(dp[-1][0])
print(*dp[-1][1][::-1])

그래프 탐색(BFS) 풀이

입력이 1일 때만 주의해서 잘 처리해주면 된다.

from collections import deque

def bfs(node, dp):
    q = deque()
    q.append((node, dp))
    while q:
        node, dp = q.popleft()
        for n in [node+1, node*2, node*3]:
            if n <= N and check[n] == 0:
                if n == N:
                    return check[node]+1, dp+[n]
                q.append((n, dp+[n]))
                check[n] = check[node]+1

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    check = [0]*(N+1)
    cnt, dp = bfs(1, [1])
    print(cnt)
    print(*dp[::-1])

S에서 시작해서 1부터 N까지 순서대로 들렀을 때의 최단거리를 구해야 되는 BFS 문제이다.

1에 들러야 된다고 해서 2를 지나가면 안 된다는 것은 아니다. 

목적지(1, 2, ... N)에 도착할 때마다 시작점부터 이동한 거리를 res에 더하고,

시작점과 목적지를 업데이트, 맵을 초기화하는 방식으로 해결했다.

EX) 시작점 S에서 목적지 1에 도착 -> res += 거리, 시작점 1, 목적지 2, 맵 초기화 

from collections import deque
from copy import deepcopy

def clear(target):
    for i in range(H):
        for j in range(W):
            if graph[i][j] == 'X':
                t[i][j] = -2
            else:
                t[i][j] = -1

def bfs(y, x, target):
    q = deque()
    q.append((y, x))
    clear(target)
    t[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < H) and (0 <= X < W) and t[Y][X] == -1:
                if graph[Y][X] == target: 
                    return t[y][x] + 1, Y, X
                else:
                    t[Y][X] = t[y][x] + 1
                    q.append((Y, X))
        
H, W, N = map(int, input().split())
graph = [list(input()) for _ in range(H)]
t = deepcopy(graph)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(H):
    for j in range(W):
        if graph[i][j] == 'S':
            y, x = i, j
            for n in range(1, N+1):
                z, y, x = bfs(y, x, str(n))
                res += z 
print(res)