[백준] 10866, 13023, 11724

덱 (10866번)

• 사이트/난이도: 백준 / 실버 4
• 코드

# 실버4 덱
import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
q = deque()

for _ in range(n):
    op = input().split()
    if len(op) == 2:
        if op[0] == "push_front":
            q.appendleft(int(op[1]))
        if op[0] == "push_back":
            q.append(int(op[1]))
    if len(op) == 1:
        if op[0] == "pop_front":
            print(-1) if not q else print(q.popleft())
        if op[0] == "pop_back":
            print(-1) if not q else print(q.pop())
        if op[0] == "size":
            print(len(q))
        if op[0] == "empty":
            print(1) if not q else print(0)
        if op[0] == "front":
            print(-1) if not q else print(q[0])
        if op[0] == "back":
            print(-1) if not q else print(q[-1])

• 느낀점
  • 일반적인 deque 문제

ABCDE (13023번)

• 사이트/난이도: 백준 / 골드5
• 코드

# 골드5 ABCDE
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n)]
visited = [False] * n
answer = False
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(number, depth):
    global answer
    visited[number] = True
    if depth == 4:
        answer = True
        return
    
    for i in graph[number]:
        if not visited[i]:
            visited[i] = True
            dfs(i, depth + 1)
            visited[i] = False

for i in range(n):
    dfs(i, 0)
    visited[i] = False
    if answer:
        print(1)
        break
if not answer:
    print(0)

• 느낀점
  • 처음에 문제를 이해 못했는데, 다시 읽어보니 dfs를 돌렸을때 깊이가 4까지 되는 관계인지 확인하는 문제였다.
  • 그냥 간단하게 dfs를 통해 구했다.

연결 요소의 개수 (11724번)

• 사이트/난이도: 백준 / 실버2
• 코드

# 실버2 연결 요소의 개수
# union-find
def find_parent(x, parent):
    if parent[x] != x:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]

def union(a, b):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
parent = [i for i in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    union(u, v)

for i in range(1, n+1):
    parent[i] = find_parent(i, parent)
print(len(set(parent[1:])))

# dfs
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

def dfs(idx):
    visited[idx] = True
    for i in graph[idx]:
        if not visited[i]:
            visited[i] = True
            dfs(i)

answer = 0
for i in range(1, n+1):
    if not visited[i]:
        answer += 1
        dfs(i)
print(answer)

• 느낀점
  • union-find, dfs 두가지 접근으로 풀어봤다.
  • 그냥 기본적인 문제였음