[Week03] 알고리즘 - DFS / BFS 백준 문제

두 문제를 구분하는 기준이 약간 모호하지만..

문제를 풀면서 만났던 몇몇 유형들을 까먹지않기 위해 정리해둔다. 

 

DFS / 백트래킹

nums = [1,2,3]
result = []
permute = []
def dfs():
    if len(permute) == len(nums) :
        result.append(permute[:])
        return
    
    for i in range(len(nums)) :
        if nums[i] not in permute :
            permute.append(nums[i])
            dfs()
            permute.pop()

dfs()
print(result)

 

DFS

25731번 : 빙산

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

2573번: 빙산

: 2차원 그래프 문제

: ❗️얼음을 순차적으로 녹이면 아직 녹지않은 얼음에도 영향이 갈 수 있기때문에 녹는 얼음들을 따로 저장해 두었다가 한 텀이 끝난 후 한꺼번에 적용해준다. 

 

 

2617번 : 구슬 찾기

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

2617번: 구슬 찾기

: 구슬을 어떤 식으로 그래프로 표현할지만 떠오르면 크게 어렵지않은 문제이다. (그게 어렵지만..)

: 구슬의 무게로 오름차순, 내림차순 그래프로 표현하여 특정 노드의 자식노드가 구슬의 n/2개 이상일때 중간에 올 수 없는 구슬이다. 

: defauldict()함수를 사용하면 편하게 딕셔너리를 사용할수이다. - 사용하지 않아도 문제없이 구현가능

light = defaultdict(list) #defauldict을 사용해서 선언 
heavy = defaultdict(list)
for i,j in biz :
    light[i].append(j) 
    heavy[j].append(i) 
    
# 키값이 없으면 빈 리스트가 저장되기때문에 
# 없는 인덱스에 접근하였을때도 에러가 나지않는다.

 

 

14888번 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

: DFS로 어떻게 구현해야하는지 잘 떠오르지않는다. 

: 이전에 순열(함수)로 해결했던 기억이 있어서 그런지 순열 밖에 떠오르지않아 백트레킹으로 모든 순열 조합을 구한다음에 연산하여 최소,최대값을 구하는 방식으로 구현하였다. > 있는 함수를 굳이 구현하여 정답은 맞았지만 어떤 메리트도 없었다. 

: dfs방식으로 풀었을 경우 완전탐색이라는 점은 똑같지만 depth를 기록하여 남아있는 모든 연산자의 경우로 가지 뻗어 나가듯이 함수를 재호출해주면서 연산을 반복하지않아되서 훨씬 효율적이다. 

 

 

 

BFS

18352번 : 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

: 시작 정점부터 n번까지 갈수 있는 노드 구하기

: while 문에 level을 세서 n번이 되면 종료되도록한다. ( bfs는 항상 최단거리를 보장한다. )

: queue(deque)를 사용하지않고 배열로만 구현하였다. 동일한 레벨이있는 노드를 전부 리스트에 담고 pop하는 대신 리스트에 들어있는 모든 노드를 검사하는 방식으로 구현하였다. 다른 더 좋은 방법이 있을지 모르겠다.

 

 

7569번 : 토마토

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

7569번: 토마토

: 3차원 그래프 - 2차원 그래프 탐색 방법에서 위아래만 추가로 확인해주면 된다.

: 빙산과 달리 한번 접근한 영역은 완료되어 재접근 하지않아도 되기 때문에 접근 확인시 바로 적용하고 visited에 체크해준다. 

:❗️시작 값을 하나씩 담으면 dfs가 한번 돌 때 인접해있는 그래프만 적용되기때문에 하루에 모든 그래프 사이클을 검사하기 위해서 모든 초기값을 큐에 append해준다. 

 

 

18405번 : 경쟁적 전염

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

18405번: 경쟁적 전염

: 단순 bfs문제라고 생각했는데 몇몇 함정이 있었다. 

: 🔑 숫자가 작은 바이러스가 먼저 퍼진다 > 우선순위 큐 사용

: 🔑 바이러스 개수만큼 반복문을 돌리는게 1초, 1초 후에 바이러스 개수를 갱신해 주는것이 핵심이다. 

 

 

2665 번 : 미로만들기

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

2665번: 미로만들기

: 우선순위 큐를 이용해 해결. 사실 아직 완전히 이해하지 못했다. 검은방의 최단경로를 확인하는거같은데..🤔🤔🤔

: 우선순위 큐가 아닌 appendleft를 사용하도 가능하다고 한다. 후에 다시 확인예정.........................

 

---

 

아직 문제를 보고 어떤 알고리즘으로 풀어야하는지 잘 떠오르지않는다... 많이 풀어보면 알수있겠지

 

스택(dfs)과 큐(bfs) 사용의 차이
스택의 경우 가능한 경로를 모두 구하는것 외에 딱히 응용할 점이 없어보인다. 큐를 사용하는 경우는, 같은 위상 순서를 가진 노드를 추출해낼 수 있다. 

 

 

문제 유형

1. 방문가능한 노드의 개수 구하기 : 방문할때 마가 cnt += 1
2. 목적지까지 도달할때 최단 거리 : 2차원 형태 : move offset 변수(dx,dy)
3. 서로 인접하지않은 지역의 개수 구하기 - 2차원 형태 : 이중 for 를 통해 방문 안한곳을 시작점으로 모두 방문
4. 정상 노드 감염시키기 - 감염된 노드들을 모두 큐에 넣고 시작한다!!
5. 동일 위치에 재방문이 가능한 경우

 

오늘도 열코!!😇😭