Jinho Tech

구현 & BFS 문제이다. 거리가 2 이상 3 이하인 노드의 개수를 출력해주면 된다.

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())
m = int(input())
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)
check[1] = 1
bfs(1)
res = sum([1 for t in check if 2 <= t <= 3])
print(res)

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

처음에 지도의 크기가 1이나 2같이 작을 경우를 고려하지 못해서 많이 틀렸다. 

입력을 받을 때 먼저 처리를 해서 -1, 0으로 이루어진 지도를 생성해서 나중에 편하게 처리한다는 점과,

t = max(map(max, a))-1
res = max(res, t)

위 코드와 2줄과 같이 map을 사용해서 보물이 묻혀 있는 두 곳 간의 최단 거리를 간단하게 찾는 부분이

핵심인 것 같다.

from collections import deque
from copy import deepcopy

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 < N) and (0 <= X < M) and a[Y][X] == 0:
                a[Y][X] = a[y][x] + 1
                queue.append((Y, X))
    
N, M = map(int, input().split())
graph = []
for _ in range(N):
    li = list(input())
    for i in range(M):
        li[i] = 0 if li[i] == 'L' else -1
    graph.append(li)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(N):
    for j in range(M):
        a = deepcopy(graph)
        if a[i][j] == 0:
            a[i][j] = 1
            bfs(i, j)
            t = max(map(max, a))-1
            res = max(res, t)
print(res)

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)

구현 & DFS & BFS 문제이다. 기업 코딩 테스트에서 나올 것 같은 문제인데 참 재밌게 푼 것 같다.

1. 터트릴 뿌요가 있는지 확인하는 함수(같은 색깔의 뿌요가 4개 이상 뭉쳐 있는지 확인)

2. 뿌요를 터트려주는 함수('RGBPY' -> '0')

3. 상태를 업데이트해주는 함수(터진 뿌요가 있을 시 그 위치보다 위에 있는 뿌요들을 밑으로 내림)

위 3개의 함수를 구현해서 해결했다.

DFS 풀이

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

def dfs_check(y, x, color, cnt):
    b[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
            cnt = dfs_check(Y, X, color, cnt+1)
    return cnt


def dfs(y, x, color):
    a[y][x] = '0'
    for dy, dx in d:
        Y, X = y+dy, x+dx
        if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
            dfs(Y, X, color)
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if dfs_check(i, j, a[i][j], 1) >= 4:
                    dfs(i, j, a[i][j])
                    ok = 1
    update()
    if ok == 0:
        break
    combo += 1
print(combo)

BFS 풀이

from collections import deque
from copy import deepcopy

def bfs_check(y, x, color):
    queue = deque()
    queue.append((y, x))
    b[y][x] = '0'
    cnt = 1
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and b[Y][X] == color:
                b[Y][X] = '0'
                queue.append((Y, X))                
                cnt += 1
    return cnt

def bfs(y, x, color):
    queue = deque()
    queue.append((y, x))
    a[y][x] = '0'
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 12) and (0 <= X < 6) and a[Y][X] == color:
                queue.append((Y, X))                
                a[Y][X] = '0'
            
def update():
    for j in range(6):
        for i in range(12):
            if a[i][j] == '0':
                up = a[0][j]
                for k in range(i):
                    down = a[k+1][j]
                    a[k+1][j] = up
                    up = down
                a[0][j] = '.'
            
graph = [list(input()) for _ in range(12)]
a = deepcopy(graph) 
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
combo = 0
while 1:    
    b, ok = deepcopy(a), 0
    for i in range(12):
        for j in range(6):
            if a[i][j] in 'RGBPY':
                if bfs_check(i, j, a[i][j]) >= 4:
                    bfs(i, j, a[i][j])
                    ok = 1                
    update()
    if ok == 0:
        break
    combo += 1
print(combo)

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

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)