✍️오늘 공부한 내용

• 백준 문제 풀이
  • 1260번 기본 DFS와 BFS
  • 1916번 최소비용 구하기
  • 7569번 토마토
  • 11724번 트리의 부모 찾기
  • 14888번 연산자 끼워넣기

📋새로 배우게 된 내용

• 오늘은 bfs와 dfs로 풀이 가능한 문제들을 많이 접했다. 문제들을 풀다보니 어느정도 패턴(?)이 생기는 거 같디. 아직 문제를 도움없이 풀기 쉽지 않지만 이 패턴을 염두해두고 코드를 짜놓으면 좋을 거 같다.
• 무한대를 표현하기 위해 1e9,-1e9 사용
• 구하라는 건 다르기때문에 응용을 해야겠지만 기본틀은 어느정도 비슷한 느낌을 받았다.
• 알고 있었는데, 오늘 문제들을 풀면서 더 뼈져리게 느꼈다. ☠️ input()보다는 sys.stdin.readline().strip()을 사용하는 습관을 들이자! (시간초과 가능성 줄임)

😜bfs , dfs 문제 풀이 방식 공통

1. vertex 방문 graph만들어주기
2. 방문여부 그래프 만들어주기
3. edge개수만큼 연결 상태 나타내기
4. 함수 선언하고 vertex인덱스 인자로 받기
5. 큐(bfs) 또는 재귀함수(dfs)로 방문여부 반영

🪄bfs 문제 풀이패턴

1. vertex를 방문했는지 여부를 나타낼 그래프를 만든다 (0,1로 연결 상태 표시) graph = [[0] * (n+1) for _ in range(n+1)]
2. 방문여부 그래프를 만들기 visited = [False] * (n+1)
3. edge개수만큼 연결 상태 표시하기 for _ in range(m): graph[a][b] = graph[b][a] = 1
4. bfs함수 선언하고 search를 시작할 vertex를 인자로 받아온다.

• 6. deque 라이브러리를 활용해서 큐를 만들고, 큐에 아무것도 없을때까지 첫번째 item을 popleft()해준다. while queue: start = queue.popleft()
• 7. 1~n번 vertex를 돌면서 방문은 안했는데 연결한 vertex를 큐에 추가해주고 방문했다고 표시해주기.

5. 첫번째 ~ n번째 vertex까지 for문 돌면서 i번쨰 방문여부 확인 if not visited[i]:BFS(i) count+=1하고, 방문하지 않은 경우 BFS를 실행

🐰 11724번 bfs

• 해당 문제는 연결된 요소를 확인하는 문제**라서 추가적으로 방문하지 않은 vertex가 생길때 (==bfs를 실행할때==edge로연결이 되어있지 않을 때)를 카운트해줌

# 연결 요소의 개수(bfs)
from sys import stdin
from collections import deque
# bfs로 문제 풀기
# 1. 그래프를 만들어주고 0과 1로 연결상태를 표시한다
# 2. 방문여부 그래프를 만들어준다 

n, m = map(int, stdin.readline().split(' '))
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)
# 3. 그래프의 연경 상태를 표시한다 
for _ in range(m):
    a, b = map(int, stdin.readline().split(' '))
    graph[a][b] = graph[b][a] = 1
 
# 4. bfs함수를 선언한다. 
# 8. bfs시작점을 인자로 받아온다.
# 9. 시작점을 담은 리스트를 deque로 만들어준다
# 10. 큐에 항목이 있을 동안 (항목==그래프의 vertex)
# 11. 처음에 있는 항목부터 pop을 하고 
# 12. 이 vertex가 방문했고 edge가 있으면 큐에 넣고
# 13. 방문했음으로 바꿔주기
def BFS(start):
    # queue = [start]
    queue = deque([start]) #deque를 사용하니까 시간이 단축되긴 함 
    while queue:
        start = queue.popleft()
        for i in range(1, n+1):
            print(i,start,visited[i],graph[start][i])
            if not visited[i] and graph[start][i] == 1:# 방문하지 않았고, 간선이 존재한다면
                queue.append(i)
                visited[i] = True
count = 0 #정답담을 개수 센 거
# 5. 첫번째 vertex시작으로부터 n번째까지 for문을 돌면서 
# 6. i번째 방문여부를 확인하고 
# 7. 방문하지 않았을 경우 BFS를 한다.
for i in range(1, n+1):
    if not visited[i]: #방문하지 않았을 경우
        BFS(i)
        count += 1
print(count)

🐰 7569번 bfs

• 해당 문제는

# x,y,z
# output = min days (-1 if impossible, 0 if ripe from start)
import sys
from collections import deque
m, n, h = map(int, input().split())  # m(x)Xn(y)Xh(z)
graph = [] 
queue = deque([])

for i in range(h):
    tmp = []
    for j in range(n):
        tmp.append(list(map(int, sys.stdin.readline().split())))
        for k in range(m):
            if tmp[j][k] == 1:
                queue.append([i, j, k])
    graph.append(tmp) #vertex 표시

dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, 1, -1, 0, 0]
dz = [0, 0, 0, 0, 1, -1]
while (queue):
    x, y, z = queue.popleft()

    for i in range(6):
        a = x+dx[i]
        b = y+dy[i]
        c = z+dz[i]
        if 0 <= a < h and 0 <= b < n and 0 <= c < m and graph[a][b][c] == 0:
            queue.append([a, b, c])
            graph[a][b][c] = graph[x][y][z]+1

day = 0
for i in graph:
    for j in i:
        for k in j:
            if k == 0:
                print(-1)
                exit(0)
        day = max(day, max(j))
print(day-1)

🪄 dfs 문제 풀이패턴

1. setrecursionlimit으로 재귀 깊이를 최대한 깊게 해서 recursion error 방지
   2 ~ 3은 bfs와 동일함!
2. dfs함수 선언하고 감색 시작 vertex를 인자로 넘겨준다.
3. queue로 구현했던 bfs와 달리 재귀를 통해 if not visited[i] and graph[start][i] == 1:DFS(i) 방문 여부를 표시해주기

🦕 11724번 dfs

import sys
sys.setrecursionlimit(10000) #python이 정한 최대 깊이를 더 깊게 변경해줌
 
n, m = map(int, sys.stdin.readline().split(' '))
graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1) #방문여부를 배열로 만들어주기
print("visited",visited)
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split(' '))
    graph[a][b] = graph[b][a] = 1 #연결된 지점 1로 표현 
print(graph) 

def DFS(start):
    visited[start] = True
    for i in range(1, n+1):
        if not visited[i] and graph[start][i] == 1:  #아직 방문하지 않았고 연결된 곳이라면
            DFS(i)
 
count = 0
for i in range(1, n+1):
    if not visited[i]:
        DFS(i)
        count += 1
print(count)

🦕 14888번 dfs

from sys import stdin
n = int(stdin.readline().strip()) #수 개수
data = list(map(int,stdin.readline().strip().split())) #수열
add,sub,mul,div=map(int,stdin.readline().strip().split()) #연산자 개수

# 최대 최소
min_val,max_val= 1e9,-1e9  #1,000,000,000

def dfs(i,arr):
    global add,sub,mul,div,max_val,min_val

    if i==n: 
        max_val=max(max_val,arr)
        min_val=min(min_val,arr)
    else:
        if add>0: # add연산자가 있다면
            add-=1
            dfs(i+1,arr+data[i])
            add+=1
        if sub>0: # sub연산자가 있다면
            sub-=1
            dfs(i+1,arr-data[i])
            sub+=1
        if mul>0: # mul연산자가 있다면
            mul-=1
            dfs(i+1,arr*data[i])
            mul+=1
        if div>0: # div연산자가 있다면
            div-=1
            dfs(i+1,int(arr/data[i]))
            div+=1

# 호출
dfs(1,data[0])
print(max_val)
print(min_val)
    

🫥오해했던 점

• deque를 쓰면 시간복잡도가 줄어든다는 건 알고 있었다. leftpop시 O(logN)인데 list로 구현 시 하나씩 밀어줘야하기 때문에 시간복잡도가 O(N)이 되버린다는 걸 직접 코드로 구현해봤다. 백준에서 다시 코드를 돌려봤는데..어? 실행시간이 더 기내🤔
• 눈으로 직접보는 걸 좋아해서 시간복잡도도 시각화할 수 없을까 고민하다가 시간복잡도를 계산할 수 있도록 코드를 짤 수 있다는 걸 알게 되었다. 다음부터는 아래의 자료를 참고해서 적용해봐야겠다!
  👉시간복잡도 계산해보기

🤯어려웠던 점

1. 아직 고민중인 부분인데, 이론 공부를 하면서 graph로 방문여부를 나타내거나 edge를 표현하면 많은 공간낭비가 일어날 수 있다는 걸 배웠었다. 실제로도 코드를 찍어보니, vertice간의 연결이 별로 없는 경우 불필요하느 공간을 만들었고 쓰이지 않았다. 메모리는 최대한 효율적으로 써야 컴퓨터도 프로세스하기 편하고 나도 오류가 적을텐데, 어떻게 이 문제를 해결할까?

😸어려움을 해결한 방법

1. 다익스트라를 공부하면서 dict형태로 edge상태를 표현할 수 있다는 걸 배웠었는데 현재 11724번 문제에 적용 중인데 시간초과가 난다. 아마도 다익스트라는 최소비용을 구하는 문제라 heapq로 우선순위를 따지는 문젠데 edge관계를 구하라는 11724번 문제와는 좀 거리가 있지 않나 생각이 들었다.

graph = {
    'A': {'B': 2, 'C': 6},
    'B': {'D': 5},
    'C': {'D': 8},
    'D': {},
}

2. 시간초과를 해결하기 위해 좀 더 고민해봐야겠다. list대신 deque사용해본다던가🤔

🤔아쉬웠던 점

• 내가 직접 짠 코드보다는 남의 코드를 보면서 공부한 시간이 많은 날이었다..아쉬운 건 내가 직접짜고 싶은 욕심(?)이 좀 났다는 점. 그래도 이런 식으로 코드를 짤 수 있구나 배울 수 있어서 좋았다.

😝느낀점

• 패턴이 어느정도 보이니까 이거에 맞게 문제에 접근하면서 연습을 하다보면 어려운 문제도 풀 수 있을 거 같아서 희망찬(?) 느낌이 들었다.

👊다짐

• 코드 이해하고 내 방식대로 짜도록 해보자!

🚀오늘의 한줄평

• bfs,dfs 좀 파악이 되는 듯!?