2021.03.10 TIL 알고리즘 공부

2021.03.10 배운 지식

-DFS (깊이 우선 탐색)

-BFS (너비 우선 탐색)

 

어제 저녁부터 계속 붙잡고 있었던 DFS, BFS ! 

9일 밤 늦게까지 꼭 한 문제를 완성시키고 자겠다는 마음으로 시도했지만 자기 전까지 완성하지 못했다.. 🤬

그런데 다음날 아침에 처음부터 다시 코딩했더니 한번에 완성됐다!! (왜.. ????!!)

 

DFS 와 BFS는 한 노드를 시작으로 인접한 다른 노드로 재귀적 탐색을 거치는 방법을 말하는데, 대표적인 예시로 알파고가 있다. 알파고는 대국을 진행하면서 발생하는 모든 수를 계산하고 최적의 수를 찾아내기 때문!

 

DFS는 한 방향으로 끝까지 파고들고 끝을 확인한 후에 가지 않은 길로 다시 가는 순서로 탐색을 진행.

BFS는 갈라진 모든 경우의 수를 탐색하며 거미줄처럼 퍼지는 순서로 탐색을 진행.

 

이 방식을 연습해보기 위해 백준 알고리즘 문제 2606번과 7576번을 코딩해봤다! 

처음 접하는 지식이라 유튜브와 강의 자료로 오랫동안 공부했고, 코딩도 많은 시간이 필요했다 😢

https://www.acmicpc.net/problem/2606

2606번: 바이러스

# 알고리즘 공부 #01
# 백준 2606

import sys
from collections import deque

def line_up():   #입력받은 컴퓨터의 연결고리들을 하나로 모아주는 함수
    global com_lined			
    while temp_q :			#먼저 들어온 순서대로 POPLEFT를 이용해 pop해주면서 끝날때까지 진행
        x,y = temp_q.popleft();    #컴퓨터 별로 연결고리를 1개씩 입력하는 문제라서 
        if y not in com_lined[x]:	#x,y로 나눠서 각각 해당하는 컴퓨터의 연결 고리에 
            com_lined[x].append(y);  # 상대가 포함되어 있는지 확인하고 없으면 넣어주도록 했다.
        if x not in com_lined[y]:
            com_lined[y].append(x);
    return

def virus(start_com):	#다음엔 바이러스가 퍼지도록 구현한 함수
    global com_lined
    global com_status
    for i in com_lined[start_com]:		#시작되는 지점을 지정해주고
        if com_status[i] == 0:			#그 컴퓨터와 연결된 모든 컴퓨터들을 하나씩 돌아가면서 확인
            com_status[i] = 1;			#해당 컴퓨터가 바이러스에 감염되지않았다면
            virus(i)					#컴퓨터 상태를 감염되었다고 바꿔주고 해당 컴퓨터 번호를
        else:							#다시 바이러스가 퍼지도록 재귀함수로 구현했다.
            continue
    return
com_num = int(sys.stdin.readline());
line_num = int(sys.stdin.readline());

lines = [list(map(int, sys.stdin.readline().split())) for _ in range(line_num)];
com_lined = [list() for _ in range(0,com_num+1)];
com_status = [0]*(com_num+1)
cnt = 0;
temp_q = deque(lines)
start_com = 1;
com_status[1] = 1;

line_up();

virus(1);

for i in com_status:
    if i == 1:
        cnt += 1
print(cnt-1);

 

사실 입력하는 방식이 굉장히 단순해서 차례 차례 검사를 진행해도 간단히 출력을 나타냈을 것 같은데, 내가 공부한 DFS,BFS의 방식을 구현해보고 싶어서 입력받은 연결 고리들을 하나씩 정리해서 각 컴퓨터에 연결된 컴퓨터가 한번에 보이도록 line_up 함수를 만들어봤다. 

내가 원하는 대로 구현이 되서 기분 좋았다 ! 

 

다음은 7576번

https://www.acmicpc.net/problem/7576

7576번: 토마토

# 알고리즘 공부 #01
# 백준 7576
import sys 
from collections import deque


#익은 토마토의 위치를 찾아 큐에 넣어주기
def find_start(t_width,t_height,lines):
    global temp_q
    for i in range(0,t_height):
        for j in range(0,t_width):
            if lines[i][j] == 1:                
                start= [i,j];
                temp_q.append(start);    
    return

#토마토가 익어 가는 함수
def go_tomato():        
    while temp_q: #큐에 익은 토마토 시작 지점이 없어질때까지 
        x,y = temp_q.popleft()        #토마토 위치 가져오기 
        for i in range(4):            #익은 토마토 위치 기준 4방향 확인
            next_x = x + x_move[i];                
            next_y = y + y_move[i];
               
            if 0<= next_x < t_height and 0<= next_y < t_width : #토마토 상자를 벗어나지 않아야함
                if lines[next_x][next_y] == 0 or lines[next_x][next_y] > lines[x][y] +1 : #익지 않았으면 혹은 이 루트가 더 빨리 익으면 
                    lines[next_x][next_y] = lines[x][y] +1;   #영향을 준 토마토의 날짜에 1을 더해서 값을 변경
                    temp_q.append([next_x,next_y])       #이번에 익은 토마토의 위치를 큐에 저장
    return                     
       
x_move = [0,0,-1,1]     #4방향 확인을 위해 설정함
y_move = [-1,1,0,0]

t_width,t_height = map(int, sys.stdin.readline().split());  #토마토 상자의 폭과 너비
#토마토 정보를 받기
lines = [list(map(int, sys.stdin.readline().split())) for _ in range(t_height)];
start = []
temp_q = deque()  #popleft를 사용하기 위해 deque 사용
find_start(t_width,t_height,lines); #익은 토마토 위치 확인
if temp_q == False :  #익은 토마토가 없으면 0을 출력
    print(0)
else : 
    go_tomato()  #토마토를 익히기
    day = max(map(max,lines)) -1   #첫날 익은 토마토의 시작 값이 1이었기때문에 제일 오래 걸린 날짜에서 -1 
    for i in range(0,t_height):    #익지 않은 토마토가 있으면 -1을 출력하고 종료
        for j in range(0,t_width):
            if lines[i][j] == 0:
                print(-1)
                exit()
    print(day)                     #모두 익었으면 걸린 날짜를 출력

 

처음에는 하루하루 토마토가 익어가고 이를 카운트해서 마지막에 걸린 day를 출력하고 싶었는데,

자꾸만 에러가 나서 아에 처음 입력했던 토마토들의 상태를 day로 사용해버렸다.

만약 빈 칸을 나타내는게 -1이 아니라 2 였다면 이 방식은 사용하기 어려울듯.. 🤔

그래도 숫자가 점점 퍼지면서 토마토가 익어가고 걸린 day를 출력하는게 귀여웠다. 

 

갈수록 내가 모르는 지식들이 나오니까 공부하는 시간도 오래걸리고 응용하기도 어려워지는 것 같다.. 

내일 동적 계획법까지 끝내면 문제 은행식으로 일주일간 배웠던 개념들을 계속 사용하는 시간이 온다.

반복해서 사용하면서 내 지식으로 만드는 방법이 최선일듯.. 

화이팅 !!