[2023 알고리즘 스터디] 1조 김동훈 4주차 - 백준 1388 2606 1260 2644

https://www.youtube.com/watch?v=1vLqC1rItM8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=18

 

 

# DFS(Depth-First Search) 깊이 우선 탐색: 그래프에서 깊은 부분을 우선적으로 탐

# 스택(혹은 재귀함수) 이용

'''

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리

2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면

   그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면

   스택에서 최상단 노드 꺼냄

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

'''

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],        #0번 노드는 비워둠(직관적으로 보기 위해)
    [2, 3, 8],  #1번 노드는 2,3,8과 연결
    [1, 7],     #2번 노드는 1,7과 연결
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

#정의된 DFS 함수 호출
dfs(graph, 1, visited)

https://www.youtube.com/watch?v=CJiF-muKz30

 

# BFS(Breadth) 너비 우선 탐색: 그래프에서 가까운 노드부터 우선적으로 탐색

# 큐 이용

'''

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은

   노드를 모두 큐에 삽입하고 방문 처리

3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복  

'''

 

 

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽임
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],         #0번 노드는 비워둠(직관적으로 보기 위해)
    [2, 3, 8],  #1번 노드는 2,3,8과 연결
    [1, 7],     #2번 노드는 1,7과 연결
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False] * 9

#정의된 BFS 함수 호출
bfs(graph, 1, visited)

https://www.youtube.com/watch?v=e7_H8SLZlHY

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

1388번: 바닥 장식

import sys
from collections import deque
input = sys.stdin.readline

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    while queue:
        x, y = queue.popleft()
        if tile[x][y] == "-":
            tile[x][y] = "1"
            if y+1 < m and tile[x][y+1] == "-":
                queue.append((x,y+1))
        elif tile[x][y] == "|":
            tile[x][y] = "1"
            if x+1 < n and tile[x+1][y] == "|":
                queue.append((x+1,y))
          
            

n, m = map(int, input().split())
tile = [list(input()) for _ in range(n)]

result = 0
for i in range(n):
    for j in range(m):
        if tile[i][j] != '1':
            bfs(i, j)
            result += 1

print(result)

중간에 있는

tile = [list(input()) for _ in range(n)]

 

은

for i in range(n):

    tile.append(list(input()))

의 코드를 간단하게 나타낸 것과 같다.

 

 

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

2606번: 바이러스

import sys
input = sys.stdin.readline

com = int(input())
connect = int(input())
net = [[] for _ in range(com + 1)]  #############

for i in range(connect):
    a, b = map(int, input().split())
    net[a].append(b)
    net[b].append(a)

count = 0
visited = [False] * (com + 1)

def dfs(start):
    global count   ################
    visited[start] = True
    for i in net[start]:
        if visited[i] == False:
            dfs(i)
            count += 1

dfs(1)
print(count)

문제를 풀면서 6번째 줄에 있는 코드(2차원 리스트 초기화)를 짤 줄 몰라서 문제를 못 풀었었는데 다행히 구글링을 통해 찾아서 문제를 해결할 수 있었다.

 

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

1260번: DFS와 BFS

 

import sys
input = sys.stdin.readline

from collections import deque

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽임
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

n, m, v = map(int, input().split())
graph = [[] for _ in range(n + 1)]

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

for i in graph:  #방문 가능 정점이 여려 개인 경우 작은 숫자부터 방문해야 하므로 오름차순 정렬
    i.sort()  

visited = [False] * (n + 1)
dfs(graph, v, visited)
print(end = '\n')

visited = [False] * (n + 1)
bfs(graph, v, visited)

이 문제는 강의에 나온 코드를 그대로 인용하는 부분이 많아 상대적으로 해결하기 수월했다.

 

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

2644번: 촌수계산

import sys
input = sys.stdin.readline

def dfs(v):
    for i in graph[v]:
        if visited[i] == 0:
            visited[i] = visited[v] + 1
            dfs(i)

n = int(input())
a, b = map(int, input().split())
m = int(input())

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

for _ in range(m):  #graph 생성
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (n + 1)
dfs(a)
print(visited[b] if visited[b] > 0 else -1)

개인적으로 이번 주에서 가장 크게 얻어가는 부분은 2차원 리스트를 생성하는 코드라고 생각한다.

DFS와 BFS에 대해서는 충분히 이해하기는 힘들었지만 2차원 리스트를 생성하는 코드라도 뇌리에 박아두어

다음에 또 사용할 일이 생기면 그 부분에서 막히지 않고 코딩을 할 수 있을 것 같다.