DFS/BFS

 

1. 프로그래머스 네트워크

핵심: 컴퓨터가 방문되지 않았다 = 그 컴퓨터가 새로운 네트워크에 속해 있다는 의미 

 DFS로 그 네트워크를 탐색한 후, 방문되는 컴퓨터가 없으면(독립적인 네트워크임) 네트워크 수를 증가시킨다

def dfs(node, visited, computers):
    visited[node] = True
    for i in range(len(computers)):
        if computers[node][i] == 1 and not visited[i]:
            dfs(i, visited, computers) # 1-2가 연결되었다면, 다시 2컴퓨터로 이동해서 dfs반족


def solution(n, computers):
    visited = [False] * n # 각 컴퓨터의 방문여부
    answer = 0

    for i in range(n):
        if not visited[i]: #방문하지 않은 컴퓨터는 dfs > 연결된 컴퓨터를 방문처리 한다
            dfs(i, visited, computers)
            answer += 1
            # 0번째 컴퓨터에 연결된 것들을 방문처리 한 후에도, 방문되지 않은 컴퓨터가 남았다는 것은
            # 그 컴퓨터는 연결된 것 없이 독립적 이라는 의미. 그래서 answer+1
            
    return answer

 

2. 프로그래머스 단어변환

최단경로를 찾는 문제 : BFS - 너비 우선 탐색이므로, 먼저 도착한 경로가 가장 짧은 경우

접근방식)

1. 시작 단어에서 변환 가능한 단어를 큐에 추가, 그 단어 각각에서 다시 변환 가능한 단어 탐색

2. 목표단어에 도달할때 까지 1번 반복

 

1)처음 풀이의 실수: count를 증가시킬때 queue에 count를 함께 담지 않고,

단어리스트에서 한글자 차이가 나는 단어를 발견할때마다 증가시킴.

> 이 방법은 탐색 중  한 글자 차이가 나는 단어가 나올 때마다 계속 count를 증가시킴 > 가장 짧은 변환횟수를 찾을 수 없다

> 다음 단어로 변환할 때마다 count를 증가시키는 방식으로 수정

 

2)BFS/DFS의 차이

BFS - 현재 깊이에 있는 모든 노드를 먼저 탐색 > 다음 깊이로 넘어감 - ex. begin에서 한번 변환하여 도달 할 수 있는 단어들을 모두 탐색 하고, 그 다음 변환으로 넘어감 - 가장 먼저 도달한 경로 = 최단 경로

DFS - 한 경로를 끝까지 탐색 한 후, 다른 경로를 탐색 - begin단어에서 target단어까지 깊게 들어가 탐색을 끝낸 뒤, 다른 경로를 시도 - 최단 경로 보장 X, 다른 경로들을 모두 탐색해야함

 

from collections import deque

def solution(begin, target, words):
    queue = deque([ (begin, 0) ]) # 현재까지 변환횟수를 함께 담는다
    visited = set() # 방문한 단어 기록

    while queue:
        current_word, count = queue.popleft()

        if current_word == target:
            return count

        for word in words:
            if word not in visited: # 방문하지 않은 단어만 탐색
                diff_count = 0
                for i in range(len(begin)):
                    if current_word[i] != word[i]:
                        diff_count += 1

                if diff_count == 1: 
                    # 한글자 차이 나는 단어가 여러개 일수도 있잖아. 
                    # 그때마다 count를 증가하는게 아니라, 단어랑 count를 함께 queue에 넣는거지
                    queue.append((word, count + 1))
                    visited.add(word) # 방문처리

    return 0 # 하나도 못찾은 경우 0 반환

 

 

3. 백준 미로탐색

N,M에 도달하기 위해 지나야 하는 최소의 칸 수  >> 2번 문제와 마찬가지로 BFS 문제임을 알아차려야 한다

from collections import deque

def bfs(matrix):
    N = len(matrix) #세로길이
    M = len(matrix[0]) #가로길이
    queue = deque([(0,0,1)]) # (x,y,이동횟수)
    visited = set((0,0))
    
    directions = [(-1,0), (0,-1), (1,0), (0,1)]
    
    while queue:
        x, y, dist = queue.popleft()

        if (x,y) == (N-1, M-1):
            return dist

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0<=nx<N and 0<=ny<M and matrix[nx][ny] == 1:
                if (nx,ny) not in visited:
                    queue.append((nx,ny,dist+1))
                    visited.add((nx,ny))

    return -1

 

4. 백준 섬의 개수

대각선도 같은 섬으로 보기 때문에, 대각선에 대한 4방향도 추가해주어야 하는 문제

def solution(matrix):
    N = len(matrix)
    M = len(matrix[0])
    queue = deque()
    visited = set()
    answer = 0
    # 상하좌우 뿐 아니라, 대각선도 같은 섬으로 보기때문에 대각선 방향도 추가해주어야 함
    directions = [(-1,0),(0,-1),(1,0),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

    for x in range(N):
        for y in range(M):
            if matrix[x][y] == 1 and (x,y) not in visited:
                queue.append((x,y))
                visited.add((x,y))
                answer += 1 # 새로운 섬 발견

                # 현재 섬에 연결된 모든 좌표 탐색 > 방문처리
                while queue:
                    a, b = queue.popleft()
                    for dx, dy in directions:
                        nx, ny = a+dx, b+dy # 첫번째 시작점의 1과 연결된 모든 1의 좌표들
                        if 0 <= nx < N and 0 <= ny < M and matrix[nx][ny] == 1 and (nx,ny) not in visited:
                            queue.append((nx,ny))
                            visited.add((nx,ny))

    return answer

 

5. 프로그래머스 타겟넘버

재귀를 사용하는 문제. 현재 숫자를 더하는 경우 / 빼는 경우를 각각 재귀적으로 탐색한다

def solution(numbers, target):
    answer = 0

    def dfs(index, current_sum):
        nonlocal answer

        if index == len(numbers): # 모든 숫자를 사용한 경우
            if current_sum == target:
                answer += 1
            return

        # 숫자를 더하는 경우, 빼는 경우 각각 재귀호출
        dfs(index + 1, current_sum + numbers[index])
        dfs(index + 1, current_sum - numbers[index])

    dfs(0,0) # 탐색 시작
    return answer

 

6. 프로그래머스 여행겅로

dfs를 재귀적으로 사용. 하나의 여행경로에 대해, 끝까지 탐색을 마친 후 다음 여행경로를 append하는 구조

from collections import defaultdict

def solution(tickets):
    graph = defaultdict(list)
    for start, end in tickets:
        graph[start].append(end)

    # 각 출발지의 도착지를 알파벳 순으로 정렬
    for key in graph.keys():
        graph[key].sort(reverse=True)  # pop()을 사용하기 위해 역순 정렬

    answer = []
    
    def dfs(start):
        while graph[start]:
            next_dest = graph[start].pop()
            dfs(next_dest)
        answer.append(start)
    
    # "ICN"에서 출발
    dfs("ICN")
    
    return answer[::-1]

 

 

7. 프로그래머스 - 게임 맵 최단거리

3번 백준 미로찾기와 똑같은 문제. 풀이방식이 완전 동일함

다만, 이전에 풀었던 방식은 

visited = [ [False for _ in range(X)] for _ in range(Y) ]

dist = [ [0 for _ in range(X)] for _ in range(Y) ]

 

dist[ny][nx] = dist[ey][ex] + 1

q.append([ny, nx])

visited[ny][nx] = True

 

이렇게 dist와 visited를 카운트하는 방식이 달랐음.

이건 풀이 방식 차이일뿐 근본적인 방식은 동일하나, 내가 실전에서 헷갈리지 않으려면 아래와 같이

visited는 set()으로, dist증가는 queue에 count변수를 추가하는 식으로 통일하자

def solution(maps):

    N = len(maps) # 행 개수
    M = len(maps[0]) # 열 개수
    visited = set((0,0))
    queue = deque([(0,0,1)]) # (x,y,이동횟수)
    directions = [(-1,0), (0,-1), (1,0), (0,1)]

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

        if (x,y) == (N-1, M-1):
            return count

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0<=nx<N and 0<=ny<M and maps[nx][ny] == 1 and (nx,ny) not in visited:
                queue.append((nx, ny, count+1))
                visited.add((nx,ny))

    return -1

---

 

 

 

[심화문제]

1. 백준 적록색약
https://www.acmicpc.net/problem/10026

- 몰랐던 함수: .copy()는 얕은복사 라서 이중리스트에는 적용 안된다
matrix_2 = [row[:] for row in matrix] # 깊은 복사를 써야함

# 적룍색약: R, G을 같은 색으로 본다
# 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수
matrix_exam = [['R','R','R','B','B'],
          ['G','G','B','B','B'],
          ['B','B','B','R','R'],
          ['B','B','R','R','R'],
          ['R','R','R','R','R']]

from collections import deque

def solution(matrix):
    N = len(matrix)
    M = len(matrix[0])

    matrix_2 = [row[:] for row in matrix]  # 깊은 복사

    def dfs(matrix, color):
        queue = deque()
        visited = set()
        res = 0

        for i in range(N):
            for j in range(M):
                if matrix[i][j] == color and (i,j) not in visited:
                    queue.append((i,j))
                    visited.add((i,j))
                    res += 1

                    while queue:
                        x, y = queue.popleft()
                        for dx, dy in [(-1,0),(0,-1),(1,0),(0,1)]:
                            nx, ny = x+dx, y+dy
                            if 0<=nx<N and 0<=ny<M and matrix[nx][ny] == color:
                                if (nx,ny) not in visited:
                                    queue.append((nx,ny))
                                    visited.add((nx,ny))
        return res

    # 적색녹약이 아닌 사람이 보는 구역 수
    def find_not_count():
        res1 = dfs(matrix, 'R')
        res2 = dfs(matrix, 'G')
        res3 = dfs(matrix, 'B')
        return res1+res2+res3 


    # 적색녹약인 사람이 보는 구역 수 구하기
    def find_count():
        for i in range(N):
            for j in range(M):
                if matrix_2[i][j] == 'G':
                    matrix_2[i][j] = 'R'
        
        res1 = dfs(matrix_2, 'R')
        res2 = dfs(matrix_2, 'B')
        return res1+res2
            

    return [find_not_count(), find_count()]

print(solution(matrix_exam))

 *** 더 간단하게 푸는법.
res1 = dfs(matrix, 'R')

res2 = dfs(matrix, 'G')

res3 = dfs(matrix, 'B')

4방향 인접범위가 시작지점의 색상과 같다는 조건을 추가하면 !!! 이렇게 각각 체크를 안해도 된다. 

def solution(matrix):
    N = len(matrix)
    M = len(matrix[0])

    matrix_2 = [row[:] for row in matrix]  # 깊은 복사

    def dfs(matrix):
        queue = deque()
        visited = set()
        res = 0

        for i in range(N):
            for j in range(M):
                if (i,j) not in visited:
                    queue.append((i,j))
                    visited.add((i,j))
                    res += 1

                    while queue:
                        x, y = queue.popleft()
                        for dx, dy in [(-1,0),(0,-1),(1,0),(0,1)]:
                            nx, ny = x+dx, y+dy
                            if 0<=nx<N and 0<=ny<M and matrix[nx][ny] == matrix[x][y]:
                                if (nx,ny) not in visited:
                                    queue.append((nx,ny))
                                    visited.add((nx,ny))
        return res

    # 적색녹약이 아닌 사람이 보는 구역 수
    def find_not_count():
        return dfs(matrix)


    # 적색녹약인 사람이 보는 구역 수 구하기
    def find_count():
        for i in range(N):
            for j in range(M):
                if matrix_2[i][j] == 'G':
                    matrix_2[i][j] = 'R'

        return dfs(matrix_2)
            

    return [find_not_count(), find_count()]

 

 

 

 

2. 프로그래머스 아이템줍기

BFS로 최단경로를 찾는 문제인데, 포인트는 좌표를 2배씩 늘려줘야 한다는 것.

그 이유는  

이 경우는 이동하면 안됨. 4방향 탐색은 한칸씩만 살펴보는데, 이 경우를 방지하기 위해 모든 좌표를 2배씩 늘려주는 것

 

좌표를 2배 늘려서 bfs를 탐색하는 것 외에는 특별한 것 없는 문제

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 좌표를 2배로 확대하여 반올림 문제를 해결
    MAX = 102  # 좌표 평면 크기
    board = [[0] * MAX for _ in range(MAX)]
    
    # 사각형 테두리를 2배 확장하여 표시
    for x1, y1, x2, y2 in rectangle:
        x1, y1, x2, y2 = x1*2, y1*2, x2*2, y2*2
        for x in range(x1, x2+1):
            for y in range(y1, y2+1):
                # 테두리 부분만 표시 (1로)
                if x == x1 or x == x2 or y == y1 or y == y2:
                    if board[x][y] != 2:  # 겹친 부분은 내부로 간주
                        board[x][y] = 1
                else:
                    board[x][y] = 2  # 내부는 2로 채워 겹침 표시

    # 시작점과 목표점도 2배 확장
    start = (characterX*2, characterY*2)
    goal = (itemX*2, itemY*2)

    # BFS 탐색
    queue = deque([(start[0], start[1], 0)])
    visited = set([start])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우 이동

    while queue:
        x, y, dist = queue.popleft()
        
        # 목표 좌표에 도달하면 경로 길이 반환 (축소하여 2로 나눔)
        if (x, y) == goal:
            return dist // 2
        
        # 네 방향으로 이동
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < MAX and 0 <= ny < MAX and board[nx][ny] == 1 and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, dist + 1))

    return -1  # 목표에 도달할 수 없는 경우

 

 

3. 프로그래머스 양과 늑대

dfs를 응용한 문제. 시간들여 원리를 이해할 필요가 있음

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

 

 

 

4. 백준 영역구하기

BFS/DFS 기본문제인데.. M,N으로 graph접근할때 i,j 순서 잘 체크해야함

실제 시험에서는 종이에 그려가면서 인덱스 접근 제대로 할것 (graph[j][i]인지, 0<=nx<M인지 N인지)

# (0,2) ~ (4,4) >> 1
M = 5 # 행의 수 (가로)
N = 7 # 열의 수 (세로)

from collections import deque

# 그래프에 1(색칠), 0(색칥X) 표기
rectangles = [ (0,2,4,4), (1,1,2,5), (4,0,6,2) ]

graph = [[0]*N for _ in range(M)]
for x1, y1, x2, y2 in rectangles:
    for i in range(y1,y2):
        for j in range(x1,x2):
            graph[i][j] = 1

count = 0
width_array = []
visited = set()
queue = deque()

for i in range(M):
    for j in range(N):
        if graph[i][j] == 0 and (i,j) not in visited:
            queue.append((i,j))
            visited.add((i,j))
            count += 1

            width = 1
            # dfs로 넓이 구하기
            while queue:
                x, y = queue.popleft()
                for dx, dy in [(-1,0),(0,-1),(1,0),(0,1)]:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<M and 0<=ny<N and (nx,ny) not in visited:
                        if graph[nx][ny] == 0:
                            queue.append((nx,ny))
                            visited.add((nx,ny))
                            width += 1
                            

            width_array.append(width)
            
print(count, sorted(width_array))