[코테 직전 유형별 정리] - DFS / BFS

코테 시즌을 맞아 내가 풀어본 문제를 유형별로 풀이 방법을 나눠보고자 한다.

이런거 커버하면 정형화된 문제는 대부분 잘 풀리는 듯?

 

---

유형 1. 그냥 탐색만 하면 되는 방식

크게 신경쓸 거 없이 그냥 탐색만 하면 되는 방식

너무 단순해서 그런가 잘 나오지는 않는 듯

 

• 게임 맵 최단거리

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

전형적인 탐색 + 이동 문제 → 장애물 피해서 목적지까지 도달하는 문제

# 칸의 최솟값
# BFS로 풀고 카운트
# 상하좌우 이동 가능

from collections import deque

def bfs(maps, n, m):
    # n-1, m-1일 때 return
    queue = deque()
    queue.append([0, 0, 0])
    direction = [[0,1],[1,0],[0,-1],[-1,0]]
    # 방문한 곳은 0으로 바꾸기
    maps[0][0] = 0
    
    while queue:
        y, x, result = queue.popleft()
        
        if y == n-1 and x == m-1:
            return result + 1
        
        
        # 상하좌우 탐색
        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            # 맵 벗어나지 않는지
            if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] != 0:
                maps[ny][nx] = 0
                queue.append([ny, nx, result + 1])
                
    return -1

def solution(maps):
    n, m = len(maps), len(maps[0])
    return bfs(maps, n, m)

 

 

 

유형 2. 이동 횟수 체크

목적지에 도달하기까지 총 몇 번 이동이 이뤄졌는지를 체크해야 하는 문제

• 특정 거리의 도시 찾기

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

단방향 그래프 주어졌을 때, n번 도시에서 출발하여 도달할 수 있는 도시 중 최단 거리가 k인 도시 모두 출력하기

"""
재귀 돌 때 cnt도 1씩 늘려주기
"""

def dfs(graph, visited, now, e, cnt):
    # 연결되어 있을 경우 바로 return 해주기
    if e in graph[now]:
        return cnt + 1

    visited[now] = True

    for node in graph[now]:
        if visited[node] == False:
            return dfs(graph, visited, node, e, cnt + 1)

 

• 단어 변환

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

begin 단어를 target으로 변환하는 가장 최소의 변환 단계 수

def bfs(begin, target, words):
    visited = []
    
    queue = deque()
    queue.append([begin, 0])
    visited.append(begin)
    
    while queue:
        now, step = queue.popleft()
        
        if now == target:
            return step
        
        # 단어 체크
        for word in words:
            if check_word(now, word) and word not in visited:
                visited.append(word)
                queue.append([word, step+1])
    
    return result

 

 

유형 3. 경로 기록

• 여행경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

dfs로 공항 탐색하면서 방문한 노드를 스택에다가 기록해주기

"""
주어진 항공권을 모두 이용하여 여행 경로를 짜기

1. defaultdict로 행선지와 티켓 개수 모두 저장하기
2. DFS로 티켓이 남은 경우 감소시키기
3. 수행 시마다 목적지 스택에 추가하기
4. 스택 뒤집어서 반환해주기
"""

def DFS(dep, graph, result):
    # 갈 수 있는 공항 탐색
    for arr in graph[dep]:
        # 아직 해당 티켓이 남았다면
        if graph[dep][arr]> 0:
            # 찾아서 1 감소
            graph[dep][arr] -= 1
            DFS(arr, graph, result)
    
    result.append(dep) # 목적지 추가

    return result

from collections import defaultdict
def solution(tickets):
    # DFS로 탐색 수행
    # 바꾼 방식 : dep : {'arr' : 1}
    graph = defaultdict(dict)
    # 해당 티켓을 딕셔너리 형태의 개수로 카운트

    for dep, arr in tickets:
        if dep not in graph.keys():
            graph[dep][arr]= 1 # 등록
        else:
            if arr not in graph[dep].keys():
                graph[dep][arr]= 1 # 등록
            else:
                graph[dep][arr] += 1 # 추가
    
    # 알파벳 순서 앞서는 경우 먼저
    # print(graph)
    for key in graph.keys():
        graph[key] = dict(sorted(graph[key].items()))
        
    # print(graph)
    answer = DFS('ICN', graph, [])
    answer.reverse() # 스택 형태이므로 다시 뒤집어서 꺼내줌
    
    return answer

 

유형 3-1. 사이클 체크 문제

• 텀 프로젝트

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

사이클이 형성되는지를 체크하는 문제 → 탐색 경로를 체크하고, 노드가 현재 경로에 있다면 사이클이 발생한것이기 때문에 사이클 부분만 잘라서 감소시키기

import sys

# 재귀 한도 설정 (기본은 1000이라 DFS 깊게 못 들어감)
sys.setrecursionlimit(10**5)

def dfs(n):
    global count

    visited[n] = True           # 현재 노드 방문 표시
    cycle_list.append(n)        # 현재 탐색 경로에 노드 추가

    # 다음 노드가 이미 방문한 노드인 경우
    if visited[arr[n]] == True:
        # 그 노드가 현재 경로(cycle_list)에 있다면 → 사이클 발생
        if arr[n] in cycle_list:
            # 사이클 부분만 잘라서 길이만큼 count 감소
            count -= len(cycle_list[cycle_list.index(arr[n]):])
        return

    else:
        # 아직 방문하지 않았다면 다음 노드로 계속 DFS
        dfs(arr[n])

# 테스트 케이스 수 입력
T = int(input())

for _ in range(T):
    N = int(input())  # 노드 수 (ex. 학생 수)

    # 입력 받은 배열을 1번 인덱스부터 사용하기 위해 맨 앞에 0 추가
    arr = [0]
    arr.extend([int(x) for x in sys.stdin.readline().rstrip().split()])

    visited = [False] * (N + 1)  # 방문 여부 초기화
    count = N                    # 전체 노드 수로 시작

    for i in range(1, N + 1):
        if not visited[i]:
            cycle_list = []      # 각 DFS마다 탐색 경로 초기화
            dfs(i)               # DFS 실행

    print(count)  # 사이클에 포함되지 않은 노드 수 출력

 

 

 

유형 4. 전염 / 최단 경로 시간 체크 유형

일자가 지날수록 전염되거나, 최종 목적지에 도달하기까지의 시간을 체크

• 토마토

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

2차원 배열 그래프가 주어지고, 모두 익을 때 까지 최소 날짜

1. 시작지점 여러 군데니까 첨에 큐에 다 때려박기
2. 상하좌우 탐색하면서 일수를 더해주고 큐에 넣기
3. 밖에서는 갱신하기

# 첫 줄에 상자 크기 나타내는 두 정수 M, N
from collections import deque

def BFS(m, n, box):
    queue = deque()
    # 2차원 box 배열 순회
    # 1인 경우 queue에 넣기, -1이 아닌 경우 상하좌우도 큐에 넣기
    # [x, y] 형태로 큐에 넣기
    # 방문한거는 2로 표시하기
	
		# 시작지점 여러 군데니까 다 큐에 때려 박아
    for x in range(n):
        for y in range(m):
            if box[x][y] == 1:
                queue.append([x, y])
    
    while queue:
        now_x, now_y = queue.popleft()
        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

        # 상하좌우 탐색하며 큐에 넣기
        # 그래프 벽도 생각해야 댐!!
        for dx, dy in direction:
            next_x, next_y = now_x + dx, now_y + dy
            # 그래프 조건을 만족하는가?
            if 0 <= next_x < n and 0 <= next_y < m:
                # 안익었으면
                if box[next_x][next_y] == 0:
                    ##### 여기 부분 중요!! ##### 더해주면서 횟수 세기 (며칠차인지 카운트)
                    box[next_x][next_y] = box[now_x][now_y] + 1
                    queue.append([next_x, next_y])
    return box


def solution(m, n, box):
    # 종료 조건 : 0이 하나도 없을 때 / (m+n) * 2까지 반복했는데도 안될 경우
    # BFS로 도달할 수 있는 경로 상하좌우에 계속해서 1을 함 (-1인 경우만 제외하고)
    # 단 -1인 경우에는 연결이 끊긴 것으로 가정하고 경로 도달 X


    # 2차원 배열 하나씩 돌면서 탐색하기
    # 시계방향으로 확인 : -1이 아닐 경우 칸에 +1 해주기
    answer = 0
    box = BFS(m,n,box)

    # 최소 일 수
    for x in range(n):
        for y in range(m):
            if box[x][y] == 0:
                return -1
        answer = max(answer, max(box[x]))
    return answer - 1

 

 

 

유형 5. 연결 그래프 탐색 문제

그래프가 연결되어있는지, 부분 그래프는 몇 개 인지 탐색하는 문제.

• 연결 요소의 개수

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

# 정점과 간선의 개수가 주어진다
# 무방향 그래프이므로 쌍방 연결 필요함
# 이것도 그 .. 덩어리 개수 구하면 되는 거 아닌가?
# 연결 요소의 개수가 뭔지가 중요할 듯

from collections import deque

# 시작노드부터 어디까지 연결되는지 카운트
# 방문하면 visited 갱신되므로 몇 번 BFS 실행되는지 세면 된다

def bfs(graph, visited, first):
    queue = deque()
    # 첫 번째 정점부터
    queue.append(first)

    while queue:
        now = queue.popleft()
        visited[now] = True

        # 인접 노드 방문
        for node in graph[now]:
            if visited[node] == False:
                queue.append(node)
								# 방문할 때 visited 넣는거 빼놓지 말아요..
                visited[node] = True

    return



def solution(n, m):
    # 그래프 생성
    graph = [[] for _ in range(n+1)]
    cnt = 0
    
    # 연결요소 입력받기
    for i in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)

    #print(graph)
    visited = [False] * (n+1)

    # 돌아가면서 시작정점 순회하기 -> 방문 안한 경우에만 bfs 시도할 것
    # bfs 실행된 횟수가 그래프 개수다~!

    for i in range(1, n+1):
        if visited[i] == False:
            bfs(graph, visited, i)
            cnt += 1

    return cnt

N, M = map(int, input().split())

print(solution(N, M))

 

• 섬의 개수

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

# 가로 세로 그리고 대각선!! 까지 가능
# 섬의 개수면 이것 역시 bfs, dfs 몇 번 실행될 수 있는가 카운트하는 문제인듯

from collections import deque

def bfs(graph, v):
    queue = deque()

    # 가로, 세로, 대각선 모두 탐색해야 함!
    # 오른쪽부터 시계방향
    direction = [[0,1],[1,1],[1,0],[1,-1],[1,0],[-1,-1],[0,-1],[-1,1]]


    # 첫 정점 넣기 & 방문 처리
    queue.append(v)
    graph[v[0]][v[1]] = 0

    while queue:
        x, y = queue.popleft()

        for dx, dy in direction:
            nx, ny = x + dx, y + dy

            # 맵을 벗어나지 않는가?
            if 0 <= nx < h and 0 <= ny < w:
                # 방문한적이 없는 섬인가?
                if graph[nx][ny] == 1:
                    queue.append([nx, ny])
                    graph[nx][ny] = 0

    return



def solution(w, h):
    # cnt
    cnt = 0

    # 맵 입력받기
    graph = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        graph[i] = list(map(int, input().split()))
    
    for i in range(h):
        for j in range(w):
            # 방문한적 없는 섬일 경우 bfs 탐색 시작
            if graph[i][j] == 1:
                bfs(graph, [i,j])
                cnt += 1
    
    return cnt


answer = []

while True:
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    answer.append(solution(w, h))

print(answer)

 

• 전력망 둘로 나누기

https://school.programmers.co.kr/learn/courses/30/lessons/86971

프로그래머스

 

from collections import deque
import copy

def bfs(graph, v):
    print('#### 시작 노드 : ', v)
    queue = deque()
    # 현재 노드 방문처리
    visited = deque()
    queue.append(v)
    
    while queue:
        node = queue.popleft()
        
        # 방문 노드 목록에 없을 경우
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
            
    print('visited ', visited)
    print('########')

    return len(visited)
    

def solution(n, wires):
    adj_list = [[] for _ in range(n+1)]
    for wire in wires:
        adj_list[wire[0]].append(wire[1])
        adj_list[wire[1]].append(wire[0])
    
    dp_list = [10001] * len(wires)
    
    for idx in range(len(wires)):
        # 인접행렬 복사
        tmp_adj_list = copy.deepcopy(adj_list)
        
        # 해당 와이어끼리 끊어야 하니까 인접노드 없애기
        x = wires[idx][0]; y = wires[idx][1]
        tmp_adj_list[x].remove(y)
        tmp_adj_list[y].remove(x)
        
        print(x, '의 인접 노드 : ', tmp_adj_list[x])
        print(y, '의 인접 노드 : ', tmp_adj_list[y])
        
        print('삭제할 전선 : ', wires[idx])
        
        area1 = bfs(tmp_adj_list, x)
        area2 = bfs(tmp_adj_list, y)
        
        print(x, area1, y, area2)
        
        dp_list[idx] = abs(area1 - area2)
    
    print(dp_list)
    return min(dp_list)

 

 

유형 6. 탐색 과정에서 최소 cost 찾기

약간 헷갈릴 수 있는데, 이동하는 칸 자체 (맵) 에 비용이 존재하는 경우 bfs로 갱신해주고 / 간선에 가중치가 있는 경우에는 다익스트라로 풀어주면 된다!

 

중요한 점은 일반 탐색과 동일하게 움직이되, 해당 위치를 최소값으로 갱신할 수 있는 경우에만 큐에 담아주면 된다.

 

• 녹색 옷 입은 애가 젤다지?

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

"""
도둑루피?!!
잃을 수밖에 없는 최소금액 - 다익스트라인지 뭔지....
0, 0 부터 n-1, n-1 까지 최소 경로
"""
from collections import deque

direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
answers = []


def bfs(graph, n):
    global direction
    queue = deque([(0, 0)])
    visited = [[-1] * n for _ in range(n)]
    visited[0][0] = graph[0][0]

    while queue:
        y, x = queue.popleft()

        for dy, dx in direction:
            ny, nx = y + dy, x + dx
            if not (0 <= ny < n and 0 <= nx < n):
                continue
            # 첫 방문
            if visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + graph[ny][nx]
                queue.append((ny, nx))
            
            # 이미 방문했다면 - 해당 위치를 최솟값으로 갱신할 수 있는 경우에만 큐에 담는다
            else:
                if visited[ny][nx] > visited[y][x] + graph[ny][nx]:
                    visited[ny][nx] = visited[y][x] + graph[ny][nx]
                    queue.append((ny, nx))

    return visited[n-1][n-1]


while True:
    n = int(input())
    if n == 0:
        break
    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))
    
    answers.append(bfs(graph, n))


for idx, a in enumerate(answers):
    print(f"Problem {idx + 1}: {a}")

 

 

유형 7. 더하고 빼서 원하는 숫자 만들기

사실 이거는 타깃 넘버빼고 본적이 없긴 한데 -- 비슷한 유형의 문제가 또 있을 것 같다.

 

• 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

더하기 빼기가 아니라 양수, 음수를 더한다는 개념으로 접근하면 쉽다.

def make_num(total, idx, target, numbers):
    # 최종적으로 도달했을 때 target num인 경우만
    if idx == len(numbers):
        if total == target:
            return 1
        else:
            return 0
    
    
    # 양수를 더하는 경우
    ret = 0
    ret += make_num(total + numbers[idx], idx+1, target, numbers)
    
    # 음수를 더하는 경우
    ret += make_num(total - numbers[idx], idx+1, target, numbers)
    
    return ret

def solution(numbers, target):
    
    return make_num(0, 0, target, numbers)

 

 

유형 8. 백트래킹

방문 경로에 대해서 visited에 넣었다 뺐다 하면서 처리하면 된다.

• 미친 로봇

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

import sys
sys.setrecursionlimit(10000)

visited = set()
answer = 0

N, e, w, s, n = map(int, input().split())
e /= 100; w /= 100; s /= 100; n /= 100 # 백분율로 고치기

def dfs(y, x, cnt, prob):
    global answer
    if cnt == N:
        answer += prob
        return
        
    # 동
    if (y, x+1) not in visited:
        visited.add((y, x+1))
        dfs(y, x+1, cnt+1, prob * e)
        visited.remove((y, x+1))
        
    # 서
    if (y, x-1) not in visited:
        visited.add((y, x-1))
        dfs(y, x-1, cnt+1, prob * w)
        visited.remove((y, x-1))
    
    # 남
    if (y+1, x) not in visited:
        visited.add((y+1, x))
        dfs(y+1, x, cnt+1, prob * s)
        visited.remove((y+1, x))
        
    # 북
    if (y-1, x) not in visited:
        visited.add((y-1, x))
        dfs(y-1, x, cnt+1, prob * n)
        visited.remove((y-1, x))
 

visited.add((0, 0)) # 미리 방문처리
dfs(0, 0, 0, 1)
print(answer)