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

이진규·2022년 7월 19일
1

백준(PYTHON)

목록 보기
55/115

1. 연결 요소의 개수(BFS)

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

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

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

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

def bfs(v):
    visited[v] = True
    q = deque([v])

    while q:
        node = q.popleft()

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

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

print(answer)

2. 2×n 타일링(DP)

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

from sys import stdin
input = stdin.readline

n = int(input())
dp = [0, 1, 2, 3]

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

print(dp[n] % 10007)

3. 2×n 타일링 2(DP)

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

  • 규칙만 빨리 찾아서 점화식을 세울 수 있다면 쉬운 문제..
from sys import stdin
input = stdin.readline

n = int(input())
dp = [0, 1, 3, 5]

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

print(dp[n] % 10007)

4. 테트로미노(★완전탐색, DFS)

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

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
pan = [ list(map(int, input().split())) for _ in range(n) ]
visited = [ [False] * m for _ in range(n) ]
answer = 0

'''
ㅗ, ㅓ, ㅏ, ㅜ 모양을 제외한 나머지 모양은 dfs를 통해서 만들 수 있는 모양이다.
그래서 dfs를 돌려 일정 깊이(cnt==4)가 되는 순간의 누적합과 비교하여 정답을 찾으면 된다.
'''

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]
def dfs(x, y, cnt, value):
    global answer
    value += pan[x][y]

    if cnt == 4: # 4번 이동했다면 누적된 값과 비교하여 저장하고 return 한다.
        answer = max(answer, value)
        return

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

        if 0 <= mx < n and 0 <= my < m:
            if not visited[mx][my]: # dfs의 경우 방문 여부를 항상 체크했다가 다시 해제해야 한다.
                visited[mx][my] = True
                dfs(mx, my, cnt+1, value)
                visited[mx][my] = False

# ㅗ, ㅏ, ㅜ, ㅓ 모양의 탐색
def move(x, y):
    global answer

    for i in range(4): # 상, 하, 좌, 우의 방향에 해당하는 반복문
        value = pan[x][y]

        for j in range(3): # 3방향의 날개에 해당하는 반복문
            mx = x + dx[(i+j)%4]
            my = y + dy[(i+j)%4]

            if not (0 <= mx < n and 0 <= my < m): # 만약 범위를 벗어나는 경우 value값을 다시 돌려놓고 break
                value = pan[x][y]
                break

            value += pan[mx][my]

        answer = max(answer, value)

for i in range(n):
    for j in range(m): # dfs의 경우 방문 여부를 항상 체크했다가 다시 해제해야 한다.
        visited[i][j] = True
        dfs(i, j, 1, 0)
        visited[i][j] = False

        move(i, j)

print(answer)

5. 비밀번호 찾기(해싱)

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

from sys import stdin
input = stdin.readline

n, m = map(int, input().split())
hash = {}

for _ in range(n):
    site, password = input().split()
    hash[site] = password

for _ in range(m):
    site = input().rstrip()

    print(hash[site])
profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글