[백준] CLASS 3 달성하기 1일차

이진규·2022년 7월 9일
1

백준(PYTHON)

목록 보기
47/115

1. 피보나치 함수(DP)

링크 : acmicpc.net/problem/1003

from sys import stdin
input = stdin.readline

T = int(input())

for _ in range(T):
    n = int(input())

    dp = [ [1, 0], [0, 1] ]

    for i in range(2, n+1):
        dp.append([ (dp[-1][0] + dp[-2][0]), (dp[-1][1] + dp[-2][1]) ])

    print(*dp[n])

2. 유기농 배추(BFS)

링크 : https://www.acmicpc.net/problem/1012


from sys import stdin
from collections import deque
input = stdin.readline

T = int(input())

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def bfs(x, y):
    visited[x][y] = True
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if 0 <= mx < n and 0 <= my < m:
                if land[mx][my] == 1 and not visited[mx][my]:
                    visited[mx][my] = True
                    q.append((mx, my))

for _ in range(T):
    m, n, k = map(int, input().split())
    answer = 0

    land = [ [0] * m for _ in range(n) ]
    visited = [ [False] * m for _ in range(n) ]

    for _ in range(k):
        a, b = map(int, input().split())
        land[b][a] = 1

    for i in range(n):
        for j in range(m):
            if land[i][j] == 1 and not visited[i][j]:
                bfs(i, j)
                answer += 1

    print(answer)

3. Z(★분할정복)

링크 : https://www.acmicpc.net/problem/1074

from sys import stdin
input = stdin.readline

n, r, c = map(int, input().split())
cnt = 0

def div_and_con(x, y, l):
    global cnt

    if x == r and y == c:
        print(cnt)
        exit(0) # return을 해주면 안되는게 내부적으로 분할정복이 계속 돌고있어 조건을 만족하면 강제종료 해줘야 함

    if l == 1: # 더이상 분할정복 할 필요가 없는 경우
        cnt += 1
        return

    if not (x <= r <= x+l and y <= c <= y+l): # 4사분면으로 나누었을때 찾고자 하는 r, c행렬이 해당 사분면 안에 없을 때 사분면 건너뛰기
        cnt += l * l
        return

    l //= 2
    div_and_con(x, y, l)
    div_and_con(x, y+l, l)
    div_and_con(x+l, y, l)
    div_and_con(x+l, y+l, l)

div_and_con(0, 0, 2**n)
print(cnt)

4. 리모컨(★완전탐색)

링크 : https://www.acmicpc.net/problem/1107

move = int(input())
n = int(input())
if n: # 고장난게 있을 경우에만 값을 입력받음
    broken = list(input().split())
else:
    broken = []

res = abs(100 - move) # 버튼을 누르지 않고 + or - 로 일일이 찾아가는 방법 (최대값)

# 작은수에서 큰수로 이동할땐 500,000 까지만 보면 되지만
# 반대로 큰수에서 작은수로 내려오는 경우가 더 최소가 될 수 있으므로 1,000,000 까지 봐야함
for i in range(1000001):
    for j in str(i):
        if j in broken: # 해당 숫자를 번호를 눌러서 만들 수 없는 경우는 스탑
            break
    else: # 번호를 만들 수 있는 경우
        # min(기존답, len(str(i)) + abs(i-move))
        res = min(res, len(str(i)) + abs(i-move))

print(res)

5. DFS와 BFS(DFS, BFS)

링크 : https://www.acmicpc.net/problem/1260

from sys import stdin
from collections import deque
input = stdin.readline

n, m, v = map(int, input().split())
graph = [ [] for _ in range(n+1) ]
answer_bfs = []
answer_dfs = []

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

for i in graph: # 정점 번호가 작은 것 부터 탐색하기 위해 미리 정렬
    i.sort()

def bfs(x): # 일반적인 BFS 방식
    visited = [False] * (n+1)
    visited[x] = True
    answer_bfs.append(x)
    q = deque([x])

    while q:
        node = q.popleft()

        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                answer_bfs.append(i)
                q.append(i)

def dfs(x): # 일반적인 DFS 방식
    visited[x] = True
    answer_dfs.append(x)

    for i in graph[x]:
        if not visited[i]:
            dfs(i)

# BFS는 함수 1번 호출에 내부 반복문 에서 visited를 쓰기 때문에 함수 내부에 visited를 생성해도 상관 없지만
# DFS는 함수를 여러번 호출 하므로 함수 외부에 visited를 생성해서 방문 여부를 체크해주는 식으로 해야 한다.
visited = [False] * (n+1)
dfs(v)
print(*answer_dfs)

bfs(v)
print(*answer_bfs)
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글