Jinho Tech

간단한 그래프 탐색 문제이다. 그냥 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)

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

DFS 풀이

import sys
sys.setrecursionlimit(300000)

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

BFS 풀이

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
            
n = int(input())
graph = [[] for _ in range(n+1)]
s, e = map(int, input().split())
for _ in range(int(input())):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(n+1)
bfs(s)
print(check[e] if check[e] > 0 else -1)

트리 & DFS & BFS 문제이다. 시간 초과를 매우 조심해야 되는 문제다. 처음에 방문 체크 리스트를 N-2번 생성하고 순서대로 체크하도록 구현했어서 그런지 시간 초과가 엄청 나왔다.

DFS 풀이

import sys
sys.setrecursionlimit(300000)

def dfs(node):
    for n in graph[node]:
        if p[n] == 0:
            p[n] = node
            dfs(n)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
p = [0]*(N+1)
dfs(1)
for i in range(2, N+1):
    print(p[i])

BFS 풀이

import sys
from collections import deque

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

N = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
p = [0]*(N+1)
bfs(1)
for i in range(2, N+1):
    print(p[i])

DFS & BFS 문제이다. 나름 짧게 잘 구현한 것 같다. 이제 좀 DFS, BFS에 익숙해진 것 같다!!

DFS 풀이

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

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

N = int(input())
graph = [list(input()) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for colors in [['R', 'G', 'B'], ["RG", 'B']]:
    t, cnt = deepcopy(graph), 0
    for i in range(N):
        for j in range(N):
            for color in colors:
                if t[i][j] in color:
                    dfs(i, j, color)
                    cnt += 1
    print(cnt, end=' ')

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs(y, x, color):
    queue = deque()
    queue.append((y, x))
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and t[Y][X] in color:
                t[Y][X] = '0'
                queue.append((Y, X))

N = int(input())
graph = [list(input()) for _ in range(N)]
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for colors in [['R', 'G', 'B'], ["RG", 'B']]:
    t, cnt = deepcopy(graph), 0
    for i in range(N):
        for j in range(N):
            for color in colors:
                if t[i][j] in color:
                    bfs(i, j, color)
                    cnt += 1
    print(cnt, end=' ')

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

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(node):
    check[node] = 1
    for n in graph[node]:
        if check[n] == 0:
            dfs(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[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
cnt = 0
for i in range(1, N+1):
    if check[i] == 0:
        dfs(i)
        cnt += 1
print(cnt)

BFS 풀이

import sys
from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = 1
                queue.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[u].append(v)
    graph[v].append(u)
check = [0]*(N+1)
cnt = 0
for i in range(1, N+1):
    if check[i] == 0:
        check[i] = 1
        bfs(i)
        cnt += 1
print(cnt)

정렬 & 자료 구조(해시) 문제이다.

N = int(input())
d = {}
for _ in range(N):
    s = input()
    d[s] = d.get(s, 0) + 1
res = sorted(d.items(), key=lambda x:x[0])
res.sort(key=lambda x:x[1], reverse=True)
print(res[0][0])

단순 정렬 문제이다.

for _ in range(int(input())):
    N = int(input())
    li = [input().split() for _ in range(N)]
    li.sort(key=lambda x:int(x[1]))
    print(li[-1][0])

DFS & BFS 문제이다.

DFS 풀이

import sys
sys.setrecursionlimit(10000)

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

while 1:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                dfs(i, j)
                cnt += 1
    print(cnt)

BFS 풀이

from collections import deque

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

while 1:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(h)]
    d = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)]
    cnt = 0
    for i in range(h):
        for j in range(w):
            if graph[i][j] == 1:
                bfs(i, j)
                cnt += 1
    print(cnt)

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

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x, cnt):
    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] == 0:
            cnt = dfs(Y, X, cnt+1)
    return cnt
    
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            res.append(dfs(i, j, 1))
print(len(res))
print(*sorted(res))

BFS 풀이

from collections import deque

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    cnt = 1
    while queue:
        y, x = queue.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:
                graph[Y][X] = 1
                queue.append((Y, X))
                cnt += 1
    return cnt
    
M, N, K = map(int, input().split())
graph = [[0]*N for _ in range(M)]
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split())
    for i in range(y1, y2):
        for j in range(x1, x2):
            graph[i][j] = 1
res = []
for i in range(M):
    for j in range(N):
        if graph[i][j] == 0:
            graph[i][j] = 1
            res.append(bfs(i, j))
print(len(res))
print(*sorted(res))

DFS & BFS 문제이다. BFS는 큐에 넣을 때 방문 표시를 해줘야 된다는 점을 항상 주의해야겠다.

큐에서 뺀 뒤에 하면 같은 좌표가 중복으로 큐에 들어가는 것이 반복된다.

DFS 풀이

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

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

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max_cnt = 1
for k in range(1, max(map(max, graph))+1):
    t = deepcopy(graph)
    cnt = 0
    for i in range(N):
        for j in range(N):
            if t[i][j] > k:
                dfs(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx            
            if (0 <= Y < N) and (0 <= X < N) and t[Y][X] > k:
                t[Y][X] = k
                queue.append((Y, X))
            
N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
max_cnt = 1
for k in range(1, max(map(max, graph))+1):
    t = deepcopy(graph)
    cnt = 0
    for i in range(N):
        for j in range(N):
            if t[i][j] > k:
                t[i][j] = k
                bfs(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)

DFS & BFS 문제이다.

BFS 풀이

from collections import deque

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

DFS 풀이

import sys
sys.setrecursionlimit(10000) 

def dfs(y, x, cnt):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    graph[y][x] = 0
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < N) and (0 <= X < M) and graph[Y][X] == 1:
            cnt = dfs(Y, X, cnt+1)
    return cnt
            
N, M, K = map(int, input().split())
graph = [[0]*M for _ in range(N)]
for _ in range(K):
    y, x = map(int, input().split())
    graph[y-1][x-1] = 1
res = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1:
            res.append(dfs(i, j, 1))
print(max(res))

DFS & BFS 문제이다. BFS로는 쉽게 통과했는데 DFS에서 계속 메모리 초과가 나온다. 한 시간 동안 해봤는데 

해결하지 못했고, 내린 결론은 BFS로 풀 수 있는 문제는 BFS로 풀어야겠다는 점이다ㅜ DFS는 BFS 보다 느리다.

BFS 풀이

from collections import deque

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

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
res = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            res.append(bfs(i, j))
print(len(res))
print(max(res) if res else 0)

단순 정렬 문제이다. 파이썬으로 정말 쉽게 풀 수 있는 문제이다.

N = int(input())
li = list(map(int,input().split()))
sorted_li = sorted(set(li))
d = {sorted_li[i]: i for i in range(len(sorted_li))}
res = [d[n] for n in li]
print(*res)

BFS 문제이다. 인접 행렬, 인접 리스트가 구조가 아닌, 1차원 리스트 구조로 BFS를 구현해주면 된다. 

from collections import deque

def bfs(N, K):
    queue = deque([N])
    while queue:
        node = queue.popleft()
        if node == K:
            return ;
        for n in [node-1, node+1, node*2]:
            if (0 <= n <= 100000) and graph[n] == 0:
                queue.append(n)
                graph[n] = graph[node] + 1
            
N, K = map(int, input().split())
graph = [0]*100001
bfs(N, K)
print(graph[K])

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

DFS 풀이

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

N = int(input())
graph = [list(map(int, list(input()))) for _ in range(N)]
res = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            res.append(dfs(i, j, 1))
res.sort()
print(len(res))
for n in res:
    print(n)

BFS 풀이

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cnt = 1
    while queue:
        y, x = queue.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:
                queue.append((Y, X))
                graph[Y][X] = 0
                cnt += 1
    return cnt

N = int(input())
graph = [list(map(int, list(input()))) for _ in range(N)]
res = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            graph[i][j] = 0
            res.append(bfs(i, j))
res.sort()
print(len(res))
for n in res:
    print(n)