본문 바로가기

BFS

[Leetcode/파이썬] 433. Minimum Genetic Mutation Minimum Genetic MutationA gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.For example, "AACCGGTT" --> "AACCGGTA" is one mutation.There is also a gene bank bank that r.. 더보기
[코딩 테스트 합격자 되기 파이썬 - 2주차]BFS 개념 문제BFS(너비 우선 탐색) 알고리즘의 작동 원리를 설명하고, 어떤 자료구조를 사용하는지, 그리고 그 이유는 무엇인지 설명해주세요.더보기BFS(너비 우선 탐색)는 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘입니다. 이를 위해 '큐' 자료구조를 채택하여 시작 노드를 큐에 넣은 다음, 방문 처리를 합니다. 이후,1. 큐가 비었는지 확인. 큐가 비었다면 방문할 수 있는 모든 노드를 방문했기 때문에 탐색을 종료합니다.2. 큐에서 노드를 팝합니다.3. 팝한 노드와 인접한 모든 노드를 확인하고 그 중 아직 방문하지 않은 노드는 큐에 푸시하여 방문처리이 과정을 반복하는 것이 BFS입니다.고려 사항으로는1. 현재 방문한 노드와 직접 연결된 모든 노드를 방문할 수 있어야 하고,2. 이미.. 더보기
[백준/파이썬][Silver I] 데스 나이트 - 16948 [Silver I] 데스 나이트 - 16948문제 링크성능 요약메모리: 114540 KB, 시간: 132 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 3월 6일 21:29:13문제 설명게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.데스 나이트는 체스판 밖으로 벗어날.. 더보기
[백준/파이썬][Gold IV] DSLR - 9019 [Gold IV] DSLR - 9019문제 링크성능 요약메모리: 216180 KB, 시간: 5032 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 4일 21:18:26문제 설명네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값.. 더보기
[백준/파이썬][Silver I] 그래프 탐색 2 - 14218 [Silver I] 그래프 탐색 2 - 14218문제 링크성능 요약메모리: 115600 KB, 시간: 232 ms분류너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2025년 2월 3일 18:31:45문제 설명남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 .. 더보기
[백준/파이썬][Gold III] 벽 부수고 이동하기 - 2206 [Gold III] 벽 부수고 이동하기 - 2206문제 링크성능 요약메모리: 277176 KB, 시간: 1320 ms분류너비 우선 탐색, 그래프 이론, 그래프 탐색제출 일자2024년 9월 22일 03:04:35문제 설명N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.한 칸에서 이동할 수 있는.. 더보기

티스토리툴바