BFS (3) 썸네일형 리스트형 [백준] 10026 적록색약 파이썬 풀이 안녕하세요? 닉네임간편입니다. 이번 시간에는 백준 10026 적록색약 문제를 풀어보겠습니다. 풀이는 파이썬으로 했고, Python3 기준으로 시간이 136ms가 나와 Pypy3으로는 돌리지 않았습니다. [문제 링크] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 접근방식 NxN 그리드의 모든 구간을 탐색해서 영역을 구해야 하기 때문에, 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 모두 사용할 수 있습니다. 그러나 전 좀 더.. [알고리즘 이론] 5. 너비 우선 탐색(BFS) 안녕하세요? 닉네임간편입니다. 이번 시간에는 너비 우선 탐색에 대해 알아보겠습니다. 1. 너비 우선 탐색이란? 너비 우선 탐색(Breadth-First Search)은 시작점에서 가까운 정점 순서대로 탐색을 하는 알고리즘입니다. 위 그림을 예시로 들어 설명하겠습니다. 시작점은 정점 1이며, 동일한 거리에 있다면 왼쪽부터 방문하도록 하겠습니다. 1) 1 -> 2 -> 3 정점 1에 인접한 정점 2와 3을 먼저 방문합니다. 정점 3을 방문한 이후 정점 1에 인접한 간선이 없으므로 해당 단계의 탐색을 종료합니다. 2) 3 -> 4 -> 5 -> 6 정점 2와 3에 인접한 정점을 왼쪽부터 순서대로 방문합니다. 정점 6을 방문한 이후 정점 2, 3에 인접한 간선이 없으므로 이 단계의 탐색을 종료합니다. 3) 6 .. [백준] 17136 색종이 붙이기 파이썬(Python3) 풀이 안녕하세요? 닉네임간편입니다. 이번 시간에는 색종이 붙이기 문제를 풀어보겠습니다. [문제 링크] https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 1. 접근 방식 1x1부터 5x5까지의 색종이로 모든 1을 덮는데 필요한 색종이의 최소 개수를 찾아야 합니다. 따라서 BFS 방식으로 접근할 수 있지만, 매번 동작을 반복할 때마다 배열의 상태를 깊은 복사 하여 전달해야 한다는 점 때문에 시간적, 공간적으로 효율적이지 않습니다. 물론 다른 방식.. 이전 1 다음
