Jinho Tech

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 'w'
    cnt = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == '-':
                q.append((Y, X))
                graph[Y][X] = 'w'
                cnt += 1
    return cnt

for _ in range(int(input())):
    N = int(input())
    graph = [list(input()) for _ in range(N)]
    d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
    res = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'w':
                res += bfs(i, j)
    print(res)

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 8) and (0 <= X < 8) and graph[Y][X] == -1:
                q.append((Y, X))
                graph[Y][X] = graph[y][x]+1

sy, sx = map(int, input().split())
ey, ex = map(int, input().split())
graph = [[-1]*8 for _ in range(8)]
d = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
bfs(sy-1, sx-1)
print(graph[ey-1][ex-1])

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < M) and (0 <= X < N):
                if graph[Y][X] == '4':
                    return graph[y][x]+1
                if graph[Y][X] == '1':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

M, N, M1, M2 = map(int, input().split())
graph = [input().split() for _ in range(M)]
d = [(-M1, -M2), (-M1, M2), (M1, -M2), (M1, M2), (-M2, -M1), (-M2, M1), (M2, -M1), (M2, M1)]
for i in range(M):
    for j in range(N):
        if graph[i][j] == '3':
            print(bfs(i, j))

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < M):
                if graph[Y][X] == 'H':
                    return graph[y][x]+1
                if graph[Y][X] == '.':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

M, N = map(int, input().split())
graph = [list(input()) for _ in range(N)]
d = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
for i in range(N):
    for j in range(M):
        if graph[i][j] == 'K':
            print(bfs(i, j))
            break

생각보다 쉬운 BFS 문제이다. 변환된 숫자와 여태까지 사용한 명령어를 큐에 같이 append, pop 해주면 된다.

변환된 숫자와 B가 같다면 여태까지 사용한 명령어(res)를 리턴하면 끝이다.

from collections import deque

def bfs(A, B):
    q = deque()
    q.append((A, ""))
    while q:
        n, res = q.popleft()
        D = n*2 % 10000
        if D == B: return res+'D'
        elif check[D] == 0:
            check[D] = 1
            q.append((D, res+'D'))
        S = n-1 if n > 0 else 9999
        if S == B: return res+'S'
        elif check[S] == 0:
            check[S] = 1
            q.append((S, res+'S'))
        L = (n%1000)*10 + n//1000
        if L == B: return res+'L'
        elif check[L] == 0:
            check[L] = 1
            q.append((L, res+'L'))
        R = (n%10)*1000 + n//10
        if R == B: return res+'R'
        elif check[R] == 0:
            check[R] = 1
            q.append((R, res+'R'))

for _ in range(int(input())):
    A, B = map(int, input().split())
    check = [0]*10000
    print(bfs(A, B))

기본적인 DFS & BFS 문제인데 DFS로는 메모리 초과 때문에 통과가 안 되는 것 같다. BFS로 제출하면 통과된다.

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '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] > '0':
                q.append((Y, X))
                graph[Y][X] = '0'

R, C = map(int, input().split())
graph = [input().split() for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
cnt = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] > '0':
            bfs(i, j)
            cnt += 1
print(cnt)

기본적인 BFS 문제이다. B에서 C로 가는 최단거리의 길이를 출력해주면 된다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 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] in ['.', 'C']:
                if graph[Y][X] == 'C':
                    return graph[y][x]+1
                q.append((Y, X))
                graph[Y][X] = graph[y][x]+1

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(R):
    for j in range(C):
        if graph[i][j] == 'B':
            print(bfs(i, j))
            break

기본적인 BFS 문제이다. 

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '.'
    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] == '*':
                q.append((Y, X))
                graph[Y][X] = '.'

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] == '*':
            bfs(i, j)
            cnt += 1
print(cnt)

기본적인 BFS 문제이다.

L(땅)이 탐지될 때마다 BFS를 돌리고 카운트를 세는데 이때 C(구름)는 L이라고 생각하고 처리하면 된다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 'W'
    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] in "LC":
                q.append((Y, X))
                graph[Y][X] = 'W'

r, c = map(int, input().split())
graph = [list(input()) for _ in range(r)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'L':
            bfs(i, j)
            cnt += 1
print(cnt)

기본적인 BFS 문제이다. 특정 노드에서부터 거리가 2 이하인 노드가 몇 개 인지 출력하면 되는 문제이다.

from collections import deque

def bfs(node):
    q = deque()
    q.append(node)
    check[node] = 0
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check[n] == -1:
                q.append(n)
                check[n] = check[node]+1

for _ in range(int(input())):
    a = input().split()
    N, M = int(a[0]), int(a[1])
    vx = a[-1]
    graph = [[] for i in range(N+1)]
    li = a[2:-1]
    for i in range(M):
        u, v = int(li[i*2][1:]), int(li[i*2+1][1:])
        graph[u].append(v)
        graph[v].append(u)
    check = [-1]*(N+1)
    bfs(int(vx[1:]))
    res = sum([1 for t in check if 1 <= t <= 2])
    print(f"The number of supervillains in 2-hop neighborhood of {vx} is {res}")

기본적인 DFS & BFS 문제이다.

처음에 그래프를 생성할 때 graph = [map(int, list(input())) for _ in range(R)] 와 같은 방식으로

생성해서 계속 메모리 초과가 나왔다. graph = [list(input()) for _ in range(R)] 로 하면 통과된다. 

DFS 풀이

import sys
from copy import deepcopy
sys.setrecursionlimit(30000000)

def dfs_check(y, x, cnt):
    a[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < S) and a[Y][X] == '1':
            cnt = dfs_check(Y, X, cnt+1)
    return cnt

def dfs(y, x, n):
    graph[y][x] = n
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < S) and graph[Y][X] == '1':
            dfs(Y, X, n)

R, S = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
li = []
a = deepcopy(graph)
for i in range(R):
    for j in range(S):
        if a[i][j] == '1':
            li.append((i, j, dfs_check(i, j, 1)))
li.sort(key=lambda x:x[2])
for i in range(len(li)):
    dfs(li[i][0], li[i][1], i+1)
for line in graph:
    print(''.join(map(str, line)))

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs_check(i, j):
    q = deque()
    q.append((i, j))
    a[i][j] = '0'
    cnt = 0
    while q:
        y, x = q.popleft()
        cnt += 1
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < S) and a[Y][X] == '1':
                a[Y][X] = '0'
                q.append((Y, X))
    return i, j, cnt

def bfs(y, x, n):
    q = deque()
    q.append((y, x))
    graph[y][x] = n
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < S) and graph[Y][X] == '1':
                graph[Y][X] = n
                q.append((Y, X))

R, S = map(int, input().split())
graph = [list(input()) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
li = []
a = deepcopy(graph)
for i in range(R):
    for j in range(S):
        if a[i][j] == '1':
            li.append(bfs_check(i, j))
li.sort(key=lambda x:x[2])
for i in range(len(li)):
    bfs(li[i][0], li[i][1], i+1)
for line in graph:
    print(''.join(map(str, line)))

단순한 BFS 문제이다. 근데 a == b일 때를 생각 못하고 처리를 안 해서 엄청나게 많이 틀렸다. 주의하도록 하자

from collections import deque

def bfs(a, b):
    q = deque()
    q.append(a)
    check[a] = 0
    while q:
        node = q.popleft()
        if node == b:
            return check[node]
        for n in graph[node]:
            if check[n] == -1:
                q.append(n)
                check[n] = check[node]+1
    return -1
    
a, b = map(int, input().split())
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    if u == v:
        continue
    graph[u].append(v)
    graph[v].append(u)
check = [-1]*(N+1)
print(bfs(a, b))

DFS & BFS 문제이다. 그런데 DFS로 풀면 시간초과가 계속 나와서 그냥 BFS로만 풀었다. 

입력을 받을 때는 sys.stdin.readline을 사용하고, Python3가 아닌 PyPy3로 제출해야 통과된다.

BFS 풀이

from collections import deque
import sys

def bfs(node):
    q = deque()
    q.append(node)
    check[node] = 1
    while q:
        node = q.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = 1
                q.append(n)

N, M = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[v].append(u)
res = []
for i in range(1, N+1):
    check = [0]*(N+1)
    bfs(i)
    res.append(check.count(1))
m = max(res)
for i in range(N):
    if res[i] == m:
        print(i+1, end=' ')
print()

기본적인 DFS & BFS 문제이다. 15092번 Sheba’s Amoebas와 같은 문제이다.

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x):
    graph[y][x] = '.'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] == '#':
            dfs(Y, X)

m, n = map(int, input().split())
graph = [list(input()) for _ in range(m)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(m):
    for j in range(n):
        if graph[i][j] == '#':
            dfs(i, j)
            cnt += 1
print(cnt)

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = '.'
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < m) and (0 <= X < n) and graph[Y][X] == '#':
                q.append((Y, X))
                graph[Y][X] = '.'

m, n = map(int, input().split())
graph = [list(input()) for _ in range(m)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 0
for i in range(m):
    for j in range(n):
        if graph[i][j] == '#':
            bfs(i, j)
            cnt += 1
print(cnt)

정렬 & DFS 문제이다. 현재 회의가 끝나는 시간이 제일 늦은 회의 시작 시간보다 크면 더 이상 회의를 할 수 없는 상황이므로 여태까지 회의에 참여한 인원수를 리스트에 추가해준다. 마지막에 리스트의 최댓값을 출력해주면 끝이다.

import sys
sys.setrecursionlimit(3000000)

def dfs(node, t):
    t += li[node][2]
    if li[node][1] > max_s:
        res.append(t)        
    for n in range(node+1, N):
        if li[node][1] > li[n][0]:
            continue
        dfs(n, t)

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
li.sort(key=lambda x:(x[0], x[1]))
res = []
max_s = max([s for s, e, n in li])
for i in range(N):
    dfs(i, 0)
print(max(res))