Jinho Tech

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

구현 & 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)

트리 & 그래프 이론 문제이다. 문제가 웃긴게 애초에 모든 국가가 연결되있기 때문에 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)

삼성 SW 역량 테스트 기출 문제로, 단순 수학 문제이다.

from math import ceil

N = int(input())
li = list(map(int, input().split()))
B, C = map(int, input().split())
res = 0
for n in li:
    n -= B
    res += 1
    if n > 0:
        res += ceil(n/C)
print(res)

구현 & 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)