Jinho Tech

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

브루트포스 알고리즘 & DFS 문제이다. 문자열 s를 계속 업데이트하다가 길이가 6이면 set(res)에 추가해주고,

마지막에 set의 길이를 출력해주면 된다.

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x, s):
    s += str(graph[y][x])
    if len(s) == 6:
        res.add(s)
        return ;
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 5) and (0 <= X < 5):
            dfs(Y, X, s)
    
graph = [list(map(int, input().split())) for _ in range(5)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = set()
for i in range(5):
    for j in range(5):
        s = ""
        dfs(i, j, s)
print(len(res))

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    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 graph[Y][X] == 'T':
                q.append((Y, X))
                graph[Y][X] = 'S'
    
while 1:
    W, H = map(int, input().split())
    if W == H == 0:
        break
    graph = [list(input()) for _ in range(H)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for i in range(H):
        for j in range(W):
            if graph[i][j] == 'S':
                bfs(i, j)
    for line in graph:
        print(''.join(line))

기본적인 BFS 문제이다.

'.'을 1, 2, 3...으로 채울 때마다 각각 몇 개를 채웠는지 확인하고, 그중 최댓값을 출력해주면 된다.

from collections import deque

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

기본적인 BFS 문제이다.

import sys
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

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[u].append(v)
    graph[v].append(u)
check = [-1]*(N+1)
bfs(1)
print(check[N] if check[N] >= 0 else -1)

생각보다 쉽지 않은 BFS 문제이다. 우선 'X'를 '1'과 '2'로 각각 채워주고, 1에서 2로 가는 최소 거리를 찾아주면 된다.

1이 1안에 갇혀서 2로 갈 수도 없는 경우가 있으므로 이 경우는 따로 잘 처리해줘야 한다.  

from collections import deque
from copy import deepcopy

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 < N) and (0 <= X < M) and graph[Y][X] == 'X':
                q.append((Y, X))
                graph[Y][X] = n
                
def bfs2(y, x):
    q = deque()
    q.append((y, x))
    a[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 a[Y][X] == '2':
                    return a[y][x]
                if a[Y][X] == '.':
                    q.append((Y, X))
                    a[Y][X] = a[y][x]+1
    return -1

N, M = map(int, input().split())
graph = [list(input()) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
cnt = 1
for i in range(N):
    for j in range(M):
        if graph[i][j] == 'X':
            bfs(i, j, str(cnt))
            cnt += 1
res = N*M
for i in range(N):
    for j in range(M):
        if graph[i][j] == '1':
            a = deepcopy(graph)
            t = bfs2(i, j)
            if t > -1:
                res = min(res, t)
print(res)

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

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(node):
    check[node] = 1
    for n in graph[node]:
        if check[n] == 0:
            dfs(n)
            
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
dfs(1)
if 0 in check[1:]:
    for i in range(1, N+1):
        if check[i] == 0:
            print(i)
else:
    print(0)

BFS 풀이

from collections import deque

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:
                q.append(n)
                check[n] = 1

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
bfs(1)
if 0 in check[1:]:
    for i in range(1, N+1):
        if check[i] == 0:
            print(i)
else:
    print(0)

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

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)

기본적인 BFS 문제이다.

from collections import deque

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

n = int(input())
graph = list(map(int, input().split()))
s = int(input())-1
check = [0]*(n)
bfs(s)
print(check.count(1))

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

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x, K, n):
    graph[y][x] = K
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] == n:
            dfs(Y, X, K, n)
            
R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
Y, X, K = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
dfs(Y, X, str(K), graph[Y][X])
for line in graph:
    print(''.join(line))

BFS 풀이

from collections import deque

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

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
Y, X, K = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
bfs(Y, X, str(K))
for line in graph:
    print(''.join(line))