코딩테스트/BFS & DFS5 [BFS] 리코쳇 로봇 https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 간단히 요약하자면, 처음 위치 R에서 목표 지점 G까지 최소 움직임을 구하는 문제다. 단 이동 할 때 한 칸씩 이동하는 게 아니라 장애물 D 이거나 board 보드를 벗어나기 전까지 멈추지 않고 쭈욱 이동한다고 보면 된다. 이때 G까지 가는 최소 움직임을 return 해주면 된다. 해설 우선, 최소 이동거리를 보장해야 하기 때문에, 너비 우선 탐색(BFS)을 사용하면 효율적이다. 이전.. 2024. 3. 7. [BFS] 미로 탈출 Lv.2 https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로.. 2024. 3. 6. [DFS] 광물캐기 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해설 접근 방식은 아래와 같다. 1. picks를 반복문으로 탐색하며 순서대로 DFS를 하기로 했다. 2. 깊이 탐색을 할 때 함수를 빠져나오는 올바른 조건을 걸어주기 3. 깊이 탐색을 할 때 피로도 계산 해주기 또 중요한 점이 하나 있는데 곡괭이의 배열이 [1, 3, 2] 이런식으로 다이아 곡괭이 1개, 철 곡괭이 3개, 돌 곡괭이 2개가 있다면 각각의 곡괭이가 아래 그림 처럼 다 다른 곡괭이.. 2024. 2. 29. [BFS] 전력망을 둘로 나누기 1. 위 문제와 같이 노드와 노드가 연결되어있는 문제의 경우, 인접관계행렬을 만들어 각 노드간 연결되어있을 경우 1, 연결되어있지 않을 경우 0으로 설정해, 배열을 만든다. 2. BFS를 이용해, 선을 하나씩 끊고, 복구하기를 반복하면서 " |두 전력망의 송전탑 개수 차| "가 가장 작은값을 반환한다. 3. BFS / DFS 모두 각 노드를 방문 했는지 안했는지를 나타내는 boolean[] visited를 생성해야 한다. 4. BFS에서는 Queue를 사용하는데, 처음 기준이 되는 노드를 넣어주고, 이 노드와 연결되어 있는 다음 노드를 추가하고 삭제하는데 사용 된다. 코드 import java.util.LinkedList; import java.util.Queue; class Solution { int[.. 2024. 2. 20. DFS / BFS DFS( 깊이 우선 탐색 , Depth-First Search) 루트 노드( 혹은 다른 임의의 노드)에서 다음 분기(branch)로 넘어가기 전에, 해당 분기(branch)를 모두 탐색하는 방법. 탐색 후에는 다시 원점으로 돌아가 다른 분기를 탐색합니다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 지닙니다. (재귀 or 스택) 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것입니다. (이를 검사하지 않을 경우 무한 루프에 빠질 수 있다. ) ex) visit[index] = true; 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와.. 2024. 1. 22. 이전 1 다음
