6/27 미경이 스터디

코변·2022년 6월 27일

오전반 - 미친경주마들

목록 보기

22/25

bfs를 접하기 전 스스로 공부해본 것들

dfs는 깊이 우선 탐색 → 노드의 끝까지 닿을 때까지 검색 후 다른 노드로 이동
bfs는 너비 우선 탐색 → 자식노드들을 모두 순회하면서 노드의 끝까지 검색
bfs는 queue와 스택을 활용하는 경우가 많음
dfs는 스택을 활용하기도 하지만 재귀함수를 쓰는 경우도 많음
부모노드와 자식노드간의 관계를 저장하는 graph 2차원 리스트를 초기화하는 경우가 많음
2차원 리스트에 양쪽 노드를 같이 넣어주고 그 값들을 순회한다.(graph[x][y] = 1 ,graph[y][x] = 1 요런 느낌적인 느낌)
문제가 다 비슷하면서도 요구하는 값이 다르기 때문에 그에 맞는 코드를 작성할 필요가 있음
이동문제는 주로 dx, dy 처럼 다음 위치에 더해져야 하는 임계값을 활용하여 답을 구한다.
dx, dy를 더한 값이 0보다 작지않고 문제에서 요구하는 리스트의 길이보다 작은지 검사한 후 문제에서 제시한 형태로 변형한다.

백준 2606 토마토

from collections import deque
def bfs(stack):
    day = 0
    while stack:
        dx = [1,-1, 0, 0, 0, 0]
        dy = [0, 0, 1, -1, 0, 0]
        dz = [0, 0, 0, 0, 1, -1]
        day +=1
        for _ in range(len(stack)):
            h_now, r_now, c_now = stack.popleft()
            for i in range(6):
                c_next = c_now + dx[i]
                r_next = r_now + dy[i]
                h_next = h_now + dz[i]
                if 0<=c_next<col and 0<=r_next<row and 0<=h_next<height and toma_box[h_next][r_next][c_next] == 0:
                    stack.append((h_next, r_next, c_next))
                    toma_box[h_next][r_next][c_next] = 1
                else:
                    continue
    for h in range(height):
        for r in range(row):
            for c in range(col):
                if toma_box[h][r][c] == 0:
                    return -1
    return day-1

col, row, height = map(int, input().split())
toma_box = [[] for _ in range(height)]
for h in range(height):
    for r in range(row):
        toma_box[h].append(list(map(int, input().split())))
stack = deque()
for h in range(height):
    for r in range(row):
        for c in range(col):
            if toma_box[h][r][c] == 1:
                stack.append((h,r,c))
print(bfs(stack))

내가 이해한 룰

주어진 3차원 리스트에 토마토의 값이 -1(없음) , 0(안익음) , 1(익음) 다음과 같이 담겨있다.
안 익은 토마토는 익은 토마토 옆에 하루만 있으면 익는다.
익은 토마토는 자신의 위 아래와 자신의 사방에만 영향을 끼친다.
모든 토마토가 익을 때까지 며칠이 걸리는지 구해야한다.
토마토가 익을 때까지의 날짜를 구할 수 없다면(연결이 되어 있지 않다면) -1을 반환하여야 한다.

문제 풀이

연결된 토마토라는 점에서 bfs를 떠올릴 수 있었고 dx, dy에 dz를 추가하여 높이값도 추가할 수 있었다.
1. 주어진 토마토 리스트에서 1인 값들의 height, row, column 값을 stack에 추가해준다.
2. 스택이 가진 값들을 하나씩 뽑아서 이동한 후의 거리를 각각 (줄인 알파벳)_next에 담고 유효성 검사를 해준다.
3. 다음 값들은 0보다는 크거나 같아야 하고 주어진 리스트의 길이보다는 작아야한다.
4. 또한 다음 값에 -1이 있거나 1이 이미 있다면 통과해준다.
5. 유효성 검사를 통과한 값들을 다시 스택에 담아주고 값을 1로 바꿔준다.
6. 만약 모든 로직을 마치고도 0이 토마토 박스에 남아있다면 -1을 프린트해주고
7. 0이 없다면 day-1값을 프린트 해준다.

추가적으로 기록할 것들

역시나 list의 pop(0)으로 앞쪽 값들을 가져왔더니 시간초과 오류가 났다.
queue를 잘 활용하자!

백준 2606 바이러스

n = int(input())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
iter_num = int(input())
for idx in range(iter_num):
    net_x,net_y = map(int, input().split())
    graph[net_x].append(net_y)
    graph[net_y].append(net_x)
stack = []
stack.append(1)
while stack:
    check_network = stack.pop(0)
    visited[check_network] = True
    for next_net in graph[check_network]:
        if not visited[next_net]:
            stack.append(next_net)
print(sum(visited)-1)