BOJ_1012 유기농 배추 - Python3

문제 접근

1. 아이디어
- BFS로 그룹 탐색
2. 복잡도
- O(V+E) : (50*50 + 4*50*50)T  >> 가능
3. 자료구조
- gragh: int[][]
- visited: bool[][]

해결 코드

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

T = int(input().strip())

for \_ in range(T):  
m, n, k = map(int, input().strip().split()) # 배추밭의 가로, 세로, 배추가 심어져 있는 위치의 개수


farm = [[0]*m for _ in range(n)]
for _ in range(k):
    x, y = map(int, input().strip().split())
    farm[y][x] = 1

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

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(y,x):
    q = deque()
    q.append([y,x])

    while q:
        y, x = q.popleft()
        visited[y][x] = True
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0<= nx <m and 0<= ny <n:
                if farm[ny][nx] == 1 and visited[ny][nx] == False:
                    visited[ny][nx] = True
                    q.append([ny,nx])

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

print(answer)

BOJ_1260 DFS와 BFS - Python3

문제 분석

1. 아이디어
- bfs
- dfs
2. 복잡도
- O(V+E): 2000 >> 가능
- V : 1000
- E : 1000
3. 자료구조
- 그래프: int[][]
- 방문기록: bool[][]

해결 코드

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

n,m,v = map(int, input().strip().split())

graph = [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = map(int, input().strip().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for e in graph:
    e.sort()

visited_b =[False]*(n+1)
visited_d =[False]*(n+1)

def dfs(start):
    visited_d[start] = True
    print(start, end=' ')
    for i in graph[start]:
        if not visited_d[i]:
            dfs(i)

def bfs(start):
    q = deque([start])
    visited_b[start] = True
    while q:
        n = q.popleft()
        print(n, end=' ')
        for i in graph[n]:
            if not visited_b[i]:
                visited_b[i] = True
                q.append(i)

dfs(v)
print()
bfs(v)

BOJ_2441 별 찍기 - 4 - Python3

문제 접근

1. 아이디어

• .rjust(n,"") 로 우측정렬, 왼쪽 채우기

2. 복잡도

• O(n) loop

3. 자료구조

• 문자열

해결 코드

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n,0,-1):
    star="*"*i
    print(star.rjust(n," "))

코멘트

• 문자열 정렬, 공백의 수, 공백 대체 포멧팅의 경우 rjust(n,"") 혹은 ljust(n,"") 활용

BOJ_10870 피보나치 수 5 - Python3

해결 코드

1) 재귀 함수

import sys
input = sys.stdin.readline

def f(n):
    if n <=1:
        return n
    return f(n-1) + f(n-2)

n = int(input())
print(f(n))

2) for loop

import sys
input = sys.stdin.readline

n = int(input())
f = [0, 1]
for i in range(2, n+1):
    num = f[i-1] + f[i-2]
    f.append(num)
print(f[n])