[알고리즘 특강] BFS, DFS 백준 문제 풀이 (4/16)

프로그래머스 코딩테스트 입문 Lv.0 풀어보기
가까운 수
https://school.programmers.co.kr/learn/courses/30/lessons/120890

파이썬
abs() : 절대값 구하기

람다식 : 간단하게 구현 가능하다
단, 함수에 대한 이해가 있어야됨

sort와 sorted 메서드
return sorted(array, key=lambda x:
(abs(n-x), x[0])
: 키값으로 결과가 아닌 뺀 값을 저장해서 뺀 값이 가장 작은 것의 key 값을 출력

: 람다식으로 간단하게 구현이 가능하다

hashmap 모르겠따

BFS, DFS 문제

백준 바이러스 2606번

완전 탐색 문제

bfs 큐
dfs 스택 둘 다로 풀 수 있는 문제임
dfs가 더 시간, 공간 효율성이 좋다 (필요없는 곳은 가지 않기 때문에)

1. bfs로 푸는 법
   내 코드 아님 강사님 코드 !!!!!!!!!

# backjoon 2606 bfs 
from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    count = 0
    while queue:
        v = queue.popleft()
        count += 1
        print(v, end=' ')
        for i in graph[v]: 
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    return count - 1

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in graph:
    i.sort()

print(bfs(graph, 1, visited))

2. dfs로 푸는 법

# backjoon 2606 dfs

def dfs(graph, v, visited):
    visited[v] = True
    count = 1
    print(v, end=' ')
    for i in range(1, len(graph)):
        if not visited[i] and graph[v][i] == 1:
            count += dfs(graph, i, visited)
    return count

n = int(input())
m = int(input())

graph = [[0] * (n+1) for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1

# print(graph)

print(dfs(graph, 1, visited) - 1)

dfs 다른 방식

# backjoon 2606 dfs Type 2
def dfs(graph, v, visited):
    visited[v] = True
    count = 1
    for i in graph[v]:
        if not visited[i]:
            count += dfs(graph, i , visited)
    return count

n = int(input())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in graph:
    i.sort()

print(dfs(graph, 1, visited) - 1)

백준 유기농 배추 1012번

한 칸 기준으로 네 방향을 다 봐야된다
dfs bfs
방문한 곳을 0 으로 처리하면 공간 덜 차지하고 해결이 가능하다
dir_column = [0, 0, -1, 1];
dir_row = [-1, 1, 0, 0]; // 네 방향 확인하는 코드

dfs였나?

import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline
MAX = 50 + 10

dir_column = [0, 0, 1, -1]
dir_row = [1, -1, 0, 0]

def dfs(graph, row, column):
    graph[row][column] = 0
    
    for i in range(4):
        next_row = row + dir_row[i]
        next_column = column + dir_column[i]
        if 0 <= next_row < n and 0 <= next_column < m and graph[next_row][next_column] == 1:
            dfs(graph, next_row, next_column)

t = int(input())

for _ in range(t):
    m, n, k = map(int, input().split())
    graph = [[0] * m for _ in range(n)]
    
    for _ in range(k):
        column, row = map(int, input().split())
        graph[row][column] = 1
    
    count = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                dfs(graph, i, j)
                count += 1
    
    print(count)