Jinho Tech

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

기본적인 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 문제이다. 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)

BFS & DFS 문제이다. 인접리스트를 행렬 형식으로 구현해서 그래프를 생성하면 쉽게 풀 수 있다.

이걸 생각못해서 1시간 넘게 뻘짓을 했다.

BFS 풀이

from collections import deque

def make_graph():
    for i in range(n+2):
        for j in range(n+2):
            if i == j:
                continue
            if abs(li[i][0]-li[j][0]) + abs(li[i][1]-li[j][1]) <= 1000:
                graph[i][j] = 1
                graph[j][i] = 1

def bfs(node):
    queue = deque()
    queue.append(0)
    while queue:
        node = queue.popleft()
        for i in range(n+2):
            if graph[node][i] == 1 and check[i] == 0:
                check[i] = 1
                queue.append(i)
        
for _ in range(int(input())):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n+2)]
    graph = [[0]*(n+2) for i in range(n+2)]
    check = [0]*(n+2)
    make_graph()
    check[0] = 1
    bfs(0)
    print("happy" if check[-1] else "sad")

DFS 풀이

def make_graph():
    for i in range(n+2):
        for j in range(n+2):
            if i == j:
                continue
            if abs(li[i][0]-li[j][0]) + abs(li[i][1]-li[j][1]) <= 1000:
                graph[i][j] = 1
                graph[j][i] = 1

def dfs(node):
    check[node] = 1
    for i in range(n+2):
        if graph[node][i] == 1 and check[i] == 0:
            dfs(i)
        
for _ in range(int(input())):
    n = int(input())
    li = [list(map(int, input().split())) for i in range(n+2)]
    graph = [[0]*(n+2) for i in range(n+2)]
    check = [0]*(n+2)
    make_graph()
    dfs(0)
    print("happy" if check[-1] else "sad")

BFS 문제이다. res.append(sum(check)-N)이 포인트인 것 같다. 

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in grpah[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
    
N, M = map(int, input().split())
grpah = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    grpah[u].append(v)
    grpah[v].append(u)
res = []
for i in range(1, N+1):
    check = [0]*(N+1)
    check[i] = 1
    bfs(i)
    res.append(sum(check)-N)
print(res.index(min(res))+1)

트리 & 그래프 이론 문제이다. 문제가 웃긴게 애초에 모든 국가가 연결되있기 때문에 N-1을 출력해면 끝이다.

처음에는 이걸 생각 못해서 두 번째 코드 같ㅇ탐색해서 풀었다.

for _ in range(int(input())):
    N, M = map(int, input().split())
    for _ in range(M):
        u, v = map(int, input().split())
    print(N-1)

import sys

def dfs(node, cnt):
    check[node] = 1
    for n in graph[node]:
        if check[n] == 0:
            cnt = dfs(n, cnt+1)
    return cnt

for _ in range(int(sys.stdin.readline())):
    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 = [0]*(N+1)
    check[1] = 0
    cnt = dfs(1, 0)
    print(cnt)

간단한 그래프 탐색 문제이다. 그냥 DFS 방식으로 풀었다.

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