알고리즘 풀이(Problem Solving)/그래프, 트리 검색 결과

해당 글 42건

알고리즘 풀이 - 백준 16954(움직이는 미로 탈출, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 8x8 크기의 체스판에서 가장 좌측 아래에 위치 시에 벽이 점점 내려오는 경우 상하좌우, 대각, 제자리의 9위치로 이동 가능 시 우측 최 상단으로 이동 가능한지 여부를 판별하는 문제 2. 풀이 이 문제는 최단 시간에 도달하는 경우를 푸는 문제는 아니지만 BFS+시뮬레이션으로 풀어야 한다. 왜냐하면, 벽이 내려올 때마다 주변의 가능한 모든 이동 가능 위치를 체크해야 하며 실제로 벽의 위치를 조정하며 문제를 해결해야 하기 때문이다. 현재 위치에서 모든 방향으로 이동 가능한 경우를 체크한 뒤, 벽이 0개 이상일 때..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 22:07

알고리즘 풀이 - 백준 16933(벽 부수고 이동하기 3, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기4 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기2 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM의 맵에서 0은 이동 가능, 1은 벽일 때, (0, 0)에서 (N-1, M-1) 위치까지 낮에만 벽을 최대 K개 부수어 도달 시 가장 최단으로 도달 가능한 경우를 구하는 문제 2. 풀이 이 문제는 벽 부수고 이동하기 2(여기 참조) 와 유사한데 낮 / 밤의 개념이 추가되어 낮에만 벽을 부술 수 있는 경우를 고려해야 하는 문제이..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 21:51

알고리즘 풀이 - 백준 14442(벽 부수고 이동하기 2, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기4 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기3 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM의 맵에서 0은 이동 가능, 1은 벽일 때, (0, 0)에서 (N-1, M-1) 위치까지 벽을 최대 K개 부수어 도달 시 가장 최단으로 도달 가능한 경우를 구하는 문제 2. 풀이 기본적으로 각 정점을 방문 시 최단 거리로 방문 가능한 경우를 찾는 문제이므로 BFS(그래프 탐색)으로 해결할 수 있다. 우선 K개의 벽을 부술 수 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 21:43

알고리즘 풀이 - 백준 16946(벽 부수고 이동하기 4, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기2 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기3 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM의 맵에서 0은 이동 가능, 1은 벽일 때, 벽이 있는 모든 위치에서 벽을 부수어 이동 시 각 위치에서 이동 가능한 블록의 개수를 행렬의 결과로 구하는 문제 2. 풀이 이 문제를 그대로 이해해서 벽으로 표시된(1로 표시된) 모든 위치를 찾아서 각 위치에서 모두 BFS를 수행하여 풀고자 할 수 있다. 다만 그렇게 하면 시간이 너..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 21:17

알고리즘 풀이 - 백준 2206(벽 부수고 이동하기, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기4 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기2 관련 포스팅은 여기를 참조 관련 문제인 벽 부수고 이동하기3 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM의 맵에서 0은 이동 가능, 1은 벽일 때, (0, 0)에서 (N-1, M-1) 위치까지 벽을 최대 1개 부수어 도달 시 가장 최단으로 도달 가능한 경우를 구하는 문제 2. 풀이 이는 주변 위치를 탐색하며 최대한 빠르게 도달할 수 있는 경우를 찾는 문제이므로 BFS로 해결할 수 있다. 모든 위치는 2가지 경우가 있다. 벽을 ..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 20:43

알고리즘 풀이 - 백준 12886(돌 그룹, 그래프(BFS, DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 돌 그룹이 3가지 있을 때, 서로 다른 2가지를 골라서 상호 연산을 수행했을 때, 모든 그룹을 같은 개수로 만들 수 있는지 여부를 확인하는 문제 2. 풀이 돌 그룹은 3가지 있는데, 이를 A, B, C라고 하자. 이 때, 각 그룹 중 2가지를 골라 서로 개수가 다르면 돌의 개수를 조정하는 연산을 수행하면 된다. 따라서 돌의 개수가 다른 모든 경우의 수를 체크하여 개수를 상호 조정하며 탐색하는 전형적인 그래프 탐색 문제이다. BFS, DFS 모든 방식으로 풀어낼 수 있다. 초반에 이 문제를 풀기 위해서 3차원의..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 6. 20:30

알고리즘 풀이 - 백준 14502(연구소, 그래프(BFS, DFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM 크기의 지도에 빈 칸, 벽, 바이러스로 이루어져 있을 때, 벽을 3개 놓을 경우 바이러스로 감염되지 않는 빈 칸(안전 영역)의 최대 크기를 구하는 문제 2. 풀이 현재 빈 칸(비 감염, 벽이 아닌 부분) 중 3군데를 고르는 모든 경우를 체크 해야 하는 문제이다. 백트래킹(벽을 세움) + 감염 위치 탐색(BFS 또는 DFS)를 통해 완전 탐색을 수행하는 문제이다. 빈 칸에 벽이 3군데 세워질 때까지 백트래킹을 통해 위치 시킨 후 현재 감염된 위치 주위를 모두 감염시킨 뒤 안전 지대 크기를 구하여 그 값이..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 5. 23:36

알고리즘 풀이 - 백준 9019(DSLR, 그래프(BFS))

관련글 그래프 관련 포스팅은 여기를 참조 DFS 관련 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 D, S, L, R이라는 명령어를 통해 숫자를 연산하는 계산기가 있을 때, A라는 숫자를 B로 만들기 위해 최소 연산을 수행하는 경우를 출력하는 문제 2. 풀이 이 문제는 전형적인 BFS 문제로 각 명령어를 통해 구한 숫자들을 탐색하고 원하는 숫자가 나올 때까지 그것을 반복하는 문제이다. 명령들은 다음과 같다. ① D : x2를 하고 10000으로 나눈 나머지를 구한다. ② S : -1을 더하되 0이된 경우 9999를 입력한다. ③ L : 좌측으로 한 칸씩 이동 ④ R : 우측으로 한 칸씩 이동 이 문제는 모..
알고리즘 풀이(Problem Solving)/그래프, 트리 2021. 4. 5. 23:18