Jinho Tech

기본적인 BFS 문제이다. 처음에 '1'의 위치들을 queue에 모두 추가해놓고 bfs를 돌리면 쉽게 풀 수 있다.

간단하지만 여태까지 풀어왔던 문제랑 조금 느낌이 달라서 푸는데 시간이 조금 걸렸다.

from collections import deque

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

n, m = map(int, input().split())
graph = [list(input()) for _ in range(n)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque()
for i in range(n):
    for j in range(m):
        if graph[i][j] == '1':
            graph[i][j] = 0
            q.append((i, j))
bfs()
for line in graph:
    print(*line)

기본적인 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 < N) and graph[Y][X] == -1:
                q.append((Y, X))
                graph[Y][X] = graph[y][x]+1

N, M = map(int, input().split())
graph = [[-1]*N for _ in range(N)]
sy, sx = map(int, input().split())
e_li = [list(map(int, input().split())) for _ in range(M)]    
d = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
bfs(sy-1, sx-1)
for y, x in e_li:
    print(graph[y-1][x-1], end=' ')
print()

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

N, K = map(int, input().split())
graph = [[] for _ in range(N+1)]
check = [-1]*(N+1)
for _ in range(K):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
ok = 1
for i in range(1, N+1):
    check = [-1]*(N+1)
    bfs(i)
    if (max(check) > 6) or (-1 in check[1:]):
        ok = 0
        break
print("Small World!" if ok else "Big World!")

기본적인 BFS 문제이다.

from collections import deque
import sys

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

N, M = map(int, sys.stdin.readline().split())
S, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
check = [-1]*(N+1)
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
cnt = bfs(S)
print(cnt)

기본적인 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)
            
while 1:
    m, n = map(int, input().split())
    if m == n == 0:
        break
    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] = '*'

while 1:
    m, n = map(int, input().split())
    if m == n == 0:
        break
    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(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 < 10) and (0 <= X < 10):
                if graph[Y][X] == 'L':
                    return graph[y][x]
                if graph[Y][X] == '.':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

graph = [list(input()) for _ in range(10)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for i in range(10):
    for j in range(10):
        if graph[i][j] == 'B':
            cnt = bfs(i, j)
print(cnt)

기본적인 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 < H) and (0 <= X < W) and graph[Y][X] == '#':
            dfs(Y, X)

for _ in range(int(input())):
    H, W = map(int, input().split())
    graph = [list(input()) for _ in range(H)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 0
    for i in range(H):
        for j in range(W):
            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 < H) and (0 <= X < W) and graph[Y][X] == '#':
                q.append((Y, X))
                graph[Y][X] = '.'

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

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

단순 수학 문제이다.

A = 1*1*...1*A 또는 A = -1*-1*...-1*A 같은 식으로도 조건을 만족하기 때문에 A'는 어떤 A''든 만들 수 있다.

for _ in range(int(input())):
    A, B = map(int, input().split())
    print("yes")

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