[항해99 취업 리부트 코스 학습일지] DFS, BFS의 재미를 잔뜩 느낀 날

그래요. 내 자랑하는겁니다.

오늘은 알고리즘 10일 차

DFS와 BFS에 대한 문제를 풀었다.

확실히 DFS, BFS가 문제가 재밌다.

정형화되면 쉽지만 조금 응용하면 또 복잡해지는 느낌 ㅎ

그래도 오늘 문제를 풀면서 많이 익숙해졌다.

재귀가 익숙하지 않아서 DFS는 재귀로 구현하려고 노력 많이 했는데 그래도 답 맞아서 다행이다 ㅎ

---

0. TIL (2024.06.10)

📚오늘 진행한 문제 리스트

1. 백준 18352 특정 거리의 도시 찾기 (실버 2) ✔️

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

풀이⬇️

# 백준 18352 특정 거리의 도시 찾기 - 실버 2

# starting point에서 부터 bfs 진행
# 진행하면서 거리가 K에 도달한 모든 point 기록

# 98816/1200
import sys
from collections import deque
input = sys.stdin.readline


def bfs(K, X, graph, visited):
    res = []
    q = deque()
    q.append((X, 0))
    visited[X] = True
    while q:
        cur, dist = q.popleft()
        if dist == K:
            res.append(cur)
            continue
        for next_target in graph[cur]:
            if not visited[next_target]:
                q.append((next_target, dist + 1))
                visited[next_target] = True
    return res


def main():
    N, M, K, X = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    visited = [False]*(N+1)
    for _ in range(M):
        start, end = map(int, input().split())
        graph[start].append(end)
    ans = sorted(bfs(K, X, graph, visited))
    return print('\n'.join(map(str, ans))) if ans else print(-1)


main()

 

2. 백준 2606 바이러스 (실버 3) ✔️

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

풀이⬇️

# 백준 2606 바이러스 - 실버 3

# bfs 진행하면서 q에 append 될 때마다 카운트 1씩 증가

# 34068/64
import sys
from collections import deque
input = sys.stdin.readline


def bfs(computers, visited):
    cnt = 0
    q = deque()
    q.append(1)
    visited[1] = True
    while q:
        cur = q.popleft()
        for nxt in computers[cur]:
            if not visited[nxt]:
                q.append(nxt)
                visited[nxt] = True
                cnt += 1
    return cnt

def main():
    n = int(input())
    m = int(input())
    computers = [[] for _ in range(n+1)]
    visited = [False] * (n+1)
    for _ in range(m):
        start, end = map(int, input().split())
        computers[start].append(end)
        computers[end].append(start)
    return print(bfs(computers, visited))


main()

 

3. 백준 21937 작업 (실버 1) ✔️

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

풀이⬇️

# 백준 21937 작업 - 실버 1

# X의 작업을 끝내기 위해서는 X 이전의 작업이 선종료가 되어야 한다.
# 그럼 역으로 X부터 시작하는 DFS 진행해서 끝 노드에 다다르면 종료

# 59036/300
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
ans = 0


def dfs(works, visited, start):
    global ans

    visited[start] = True
    for nxt in works[start]:
        if not visited[nxt]:
            ans += 1
            dfs(works, visited, nxt)


def main():
    N, M = map(int, input().split())
    works = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    for _ in range(M):
        start, end = map(int, input().split())
        works[end].append(start)
    X = int(input())
    dfs(works, visited, X)
    return print(ans)


main()

 

4. 백준 25195 Yes or yes (골드 4) ✔️

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

풀이⬇️

# 백준 25195 Yes or yes - 골드 4

# dfs/bfs 둘 다 풀 수 있는 문제 -> dfs 풀이 진행(재귀에 약해서..)
# 그래프를 순회하면서 팬클럽 곰곰이가 있는 지점에 도착했는지 여부에 따라 True/False 기록
# True가 하나라도 있으면 진행이 가능하단 뜻이므로 yes 아니라면 Yes

# 66572/264
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

result = []


def dfs(destinations, visited, existed_points, start):
    global result

    if start in existed_points:
        result.append(False)
        return

    if not destinations[start]:
        result.append(True)
        return

    visited[start] = True
    for dest in destinations[start]:
        if not visited[dest]:
            dfs(destinations, visited, existed_points, dest)


def main():
    N, M = map(int, input().split())
    destinations = [[] for _ in range(N+1)]
    visited = [False] * (N+1)
    for _ in range(M):
        start, end = map(int, input().split())
        destinations[start].append(end)
    S = int(input())
    existed_point = list(map(int, input().split()))
    dfs(destinations, visited, existed_point, 1)
    return print('Yes') if all(not r for r in result) else print('yes')


main()

 

5. 백준 1240 노드사이의 거리 (골드 5) ✔️

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

풀이⬇️

# 백준 1240 노드사이의 거리 - 골드 5

# 주어진 트리를 양방향으로 연결하고 이를 dfs로 탐색하면서 내가 찾는 end까지 도달하면 거기에 해당하는 result 리턴
# tree를 전부 0으로 채워넣으니까 시간초과 -> 해당하는 값만 넣기

# 31120/180
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

result = 0
flag = False


def make_the_tree(arr, N):
    for _ in range(N - 1):
        start, end, dist = map(int, input().split())
        arr[start].append((end, dist))
        arr[end].append((start, dist))
    return arr


def dfs(tree, nodes, visited, cnt):
    global result, flag

    start, end = nodes
    visited[start] = True

    if start == end:
        flag = True
        result = cnt
        return

    for val in tree[start]:
        s, d = val
        if not visited[s]:
            dfs(tree, (s, end), visited, cnt + d)
            if flag:
                return


def main():
    global result, flag

    N, M = map(int, input().split())
    tree = make_the_tree([[] for _ in range(N+1)], N)
    answer = []
    for _ in range(M):
        visited = [False] * (N+1)
        nodes = map(int, input().split())
        dfs(tree, nodes, visited, 0)
        answer.append(result)
        result, flag = 0, False
    return print('\n'.join(map(str, answer)))


main()

 

6. 백준 7569 토마토 (골드 5) ✔️

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

풀이⬇️

# 백준 7569 토마토 - 골드 5

# 방향을 6개 지정 (전후좌우상하) -> BFS로 육방탐색 진행

# 50560/2064
import sys
from collections import deque

input = sys.stdin.readline

dx, dy, dz = [0, 0, 0, 1, 0, -1], [0, 0, -1, 0, 1, 0], [-1, 1, 0, 0, 0, 0]


def search_of_the_six_directions(tomatoes, q, cnt):
    days = 0
    while q:
        z, y, x, day = q.popleft()
        for d in range(6):
            nx, ny, nz = x + dx[d], y + dy[d], z + dz[d]
            if (0 <= nx < len(tomatoes[0][0])
                    and 0 <= ny < len(tomatoes[0])
                    and 0 <= nz < len(tomatoes)
                    and not tomatoes[nz][ny][nx]):
                q.append((nz, ny, nx, day + 1))
                tomatoes[nz][ny][nx] = 1
                cnt -= 1
                days = day + 1

    return -1 if cnt else days


def main():
    M, N, H = map(int, input().split())
    tomatoes = [[list(map(int, input().split())) for _ in range(N)] for _ in range(H)]
    q = deque()
    cnt = 0
    for i in range(H):
        for j in range(N):
            for k in range(M):
                if tomatoes[i][j][k] == 1:
                    q.append((i, j, k, 0))
                elif not tomatoes[i][j][k]:
                    cnt += 1
    return print(search_of_the_six_directions(tomatoes, q, cnt)) if cnt else print(0)


main()

 

7. 백준 10026 적록색약 (골드 5) ✔️

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

풀이⬇️

# 백준 10026 적록색약 - 골드 5

# bfs -> 각 구역에 따른 사방탐색 진행
# 먼저 기존 grid 구하고 그 다음에 적록색맹 구한다.

# 34096/88
import sys
from collections import deque

input = sys.stdin.readline

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]


def bfs(N, grid):
    res = 0
    visited = [[False] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                q = deque([(i, j)])
                visited[i][j] = True
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        nx, ny = x + dx[d], y + dy[d]
                        if (0 <= nx < len(grid)
                                and 0 <= ny < len(grid[0])
                                and grid[x][y] == grid[nx][ny]
                                and not visited[nx][ny]):
                            q.append((nx, ny))
                            visited[nx][ny] = True
                res += 1
    return res


def change_val(N, grid):
    for i in range(N):
        for j in range(N):
            if grid[i][j] == 'G':
                grid[i][j] = 'R'


def main():
    N = int(input())
    grid = [[x for x in input().strip()] for _ in range(N)]
    original = bfs(N, grid)
    change_val(N, grid)
    color_blindness = bfs(N, grid)
    return print(original, color_blindness)


main()

 

8. 백준 3055 탈출 (골드 4) ✔️

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

풀이⬇️

# 백준 3055 탈출 - 골드 4

# 이동하지 못하는 조건
# 1. X or * 일때
# 2. 범위 밖일 때
# 3. 방문 했을 때
# 4. current = '*' 인데 D로 가려고 할 때

# bfs 진행하면서 물 -> 고슴도치 순으로 진행 (물이 간 위치는 갈 수 없음)

# 34116/64
import sys
from collections import deque

input = sys.stdin.readline

dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]


def find_coordinates(row, col, forest, visited, q):
    for i in range(row):
        for j in range(col):
            if forest[i][j] == 'S':
                q.append((i, j))
                visited[i][j] = 0
            if forest[i][j] == '*':
                q.appendleft((i, j))


def bfs(q, forest, visited):
    while q:
        x, y = q.popleft()
        current = forest[x][y]
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]

            if (0 <= nx < len(forest)
                    and 0 <= ny < len(forest[0])
                    and forest[nx][ny] != 'X'
                    and forest[nx][ny] != '*'
                    and visited[nx][ny] == -1
                    and not (current == '*' and forest[nx][ny] == 'D')):

                if current == 'S':
                    if forest[nx][ny] == 'D':
                        return visited[x][y] + 1
                    visited[nx][ny] = visited[x][y] + 1
                forest[nx][ny] = current
                q.append((nx, ny))
    return 'KAKTUS'


def main():
    R, C = map(int, input().split())
    map_of_forest = [[x for x in input().strip()] for _ in range(R)]
    visited = [[-1] * C for _ in range(R)]
    q = deque()
    find_coordinates(R, C, map_of_forest, visited, q)
    return print(bfs(q, map_of_forest, visited))


main()

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• DFS, BFS

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 재귀 문제 풀 때, sys.setrecursionlimit(10**7) 꼭 적고 풀기(파이썬 재귀 제한 때문에)

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지