Jinho Tech

기본적인 BFS 문제이다.

from collections import deque

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

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 문제이다.

from collections import deque
from copy import deepcopy

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

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
check = [[-1]*M for _ in range(N)]
res = 0
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            a = deepcopy(check)
            res = max(res, bfs(i, j))
print(res)

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

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x, cnt):
    c = graph[y][x]
    graph[y][x] = 1
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == c:
            cnt = dfs(Y, X, cnt+1)
    return cnt

N, M = map(int, input().split())
graph = [list(input()) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
w = b = 0
for i in range(M):
    for j in range(N):
        if graph[i][j] == 'W':
            w += dfs(i, j, 1)**2
        elif graph[i][j] == 'B':
            b += dfs(i, j, 1)**2
print(w, b)

BFS 풀이

from collections import deque

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

N, M = map(int, input().split())
graph = [list(input()) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
w = b = 0
for i in range(M):
    for j in range(N):
        if graph[i][j] == 'W':
            w += bfs(i, j)**2
        elif graph[i][j] == 'B':
            b += bfs(i, j)**2
print(w, b)

기본적인 BFS 문제이다. 양과 늑대가 인접해있으면 막을 수가 없으므로 0을 출력해주고,

인접한 경우가 없다면 늑대를 가둬버리고 결과를 출력해주면 된다.

from collections import deque

def bfs(y, x):
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < R) and (0 <= X < C):
            if graph[Y][X] == 'S':
                return False
            if graph[Y][X] == '.':
                graph[Y][X] = 'D'
    return True

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):
        t = True
        if graph[i][j] == 'W':
            t = bfs(i, j)
            if t == False:
                print(0)
                break
if t:
    print(1)
    for line in graph:
        print(''.join(line))

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

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

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

M, N = map(int, input().split())
graph = [list(map(int, input().split())) 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] == 1:
            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] = 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) and graph[Y][X] == 1:
                q.append((Y, X))
                graph[Y][X] = 0

M, N = map(int, input().split())
graph = [list(map(int, input().split())) 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] == 1:
            bfs(i, j)
            cnt += 1
print(cnt)

생각보다 어려운 BFS 문제이다. 바이러스가 퍼지는 순서(작은 숫자부터)에 맞게

def bfs(x, y):
    check[x][y] = 1
    for dx, dy in d:
        X, Y = x+dx, y+dy
        if (0 <= X < N) and (0 <= Y < N) and graph[X][Y] == 0:
            check[X][Y] = 1
            graph[X][Y] = graph[x][y]

N, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
S, X, Y = map(int, input().split())
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
check = [[0]*N for _ in range(N)]
while S:
    li = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] > 0:
                li.append([i, j])
    li.sort(key=lambda x:graph[x[0]][x[1]])
    for i, j in li:
        bfs(i, j)
    if graph[X-1][Y-1]:
        break
    S -= 1
print(graph[X-1][Y-1])

기본적인 DFS & BFS 문제이다. 3184번 양과 거의 동일한 문제이다. 그냥 BFS으로만 풀었다. 

BFS 풀이

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    s = w = 0
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != '#' and check[Y][X] == 0:
                if graph[Y][X] == 'k':
                    s += 1
                elif graph[Y][X] == 'v':
                    w += 1
                check[Y][X] = 1
                queue.append((Y, X))
    return s, w

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
check = [[0]*(C) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
S = W = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] != '#' and check[i][j] == 0:
            s = w = 0    
            if graph[i][j] == 'k':
                s += 1
            elif graph[i][j] == 'v':
                w += 1
            check[i][j] = 1
            a, b = bfs(i, j)
            s, w = s+a, w+b
            if s > w:
                w = 0
            else:
                s = 0
            S += s
            W += w
print(S, W)

기본적인 BFS 문제이다.

from collections import deque

def bfs(node):
    q = deque()
    q.append(node)
    graph[node] = 0
    while q:
        node = q.popleft()
        for n in [node-1, node+1, node+A, node-A, node+B, node-B, node*A, node*B]:
            if (0 <= n <= 100000) and graph[n] == -1:
                q.append(n)
                graph[n] = graph[node]+1
                if n == M:
                    return ;

A, B, N, M = map(int, input().split())
graph = [-1]*100001 
bfs(N)
print(graph[M])

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

첫번째 줄만 탐색을 시킨 후에 마지막 줄이 탐색이 된 적 있으면 "YES" 아니면 "NO"를 출력해주면 된다.

DFS 풀이

import sys
sys.setrecursionlimit(3000000)

def dfs(y, x):
    graph[y][x] = 2
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < M) and (0 <= X < N) and graph[Y][X] == 0:
            dfs(Y, X)
            
M, N = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for j in range(N):
    if graph[0][j] == 0:
        dfs(0, j)
print("YES" if 2 in graph[-1] else "NO")

BFS 풀이

from collections import deque
def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 2
    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] == 0:
                q.append((Y, X))
                graph[Y][X] = 2
            
M, N = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(M)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for j in range(N):
    if graph[0][j] == 0:
        bfs(0, j)
print("YES" if 2 in graph[-1] else "NO")

기본적인 BFS 문제이다. 

from collections import deque

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

기본적인 BFS 문제이다. 

from collections import deque

def bfs(r, c):
    q = deque()
    q.append((r, c))
    graph[r][c] = 0
    while q:
        r, c = q.popleft()
        for dr, dc in d:
            R, C = r+dr, c+dc
            if (0 <= R < N) and (0 <= C < N) and graph[R][C] == -1:
                q.append((R, C))
                graph[R][C] = graph[r][c]+1

N = int(input())
sr, sc, er, ec = map(int, input().split())
graph = [[-1]*(N) for _ in range(N)]
d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]
bfs(sr, sc)
print(graph[er][ec])

기본적인 BFS 문제이다. 

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

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

기본적인 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:
                check[n] = check[node]+1
                q.append(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)
bfs(1)
m = max(check)
print(check.index(m), m-1, check.count(m))

그리디 알고리즘 & BFS 문제이다.

from collections import deque

def bfs(A, B):
    cnt = 1
    queue = deque()
    queue.append((A, cnt))
    while queue:
        node, cnt = queue.popleft()
        if node == B:
            return cnt
        if node*2 <= B:
            queue.append((node*2, cnt+1))
        if int(str(node)+'1') <= B:
            queue.append((int(str(node)+'1'), cnt+1))
    return -1

A, B = map(int, input().split())
print(bfs(A, B))

BFS 문제이다. bfs탐색으로 각 울타리 영역의 양과, 늑대('o'와 'v')의 수를 센 후에,

각 울타리당 양의 수가 늑대보다 많으면 늑대를 0으로, 아니면 양을 0으로 바꿔주고 그 총합을 출력해주면 된다.

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    s = w = 0
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != '#' and check[Y][X] == 0:
                if graph[Y][X] == 'o':
                    s += 1
                elif graph[Y][X] == 'v':
                    w += 1
                check[Y][X] = 1
                queue.append((Y, X))
    return s, w

R, C = map(int, input().split())
graph = [list(input()) for _ in range(R)]
check = [[0]*(C) for _ in range(R)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
S = W = 0
for i in range(R):
    for j in range(C):
        if graph[i][j] != '#' and check[i][j] == 0:
            s = w = 0    
            if graph[i][j] == 'o':
                s += 1
            elif graph[i][j] == 'v':
                w += 1
            check[i][j] = 1
            a, b = bfs(i, j)
            s, w = s+a, w+b
            if s > w:
                w = 0
            else:
                s = 0
            S += s
            W += w
print(S, W)