반응형 BFS19 [프로그래머스/C++] 지형 이동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떻게 풀지 고민했다. 처음에는 특정 사다리를 놓을 경우 최소값만 구하려고 했는데, 그렇게 풀면 최소값을 구하는 과정에서 A, B, C 지역이 전부 연결되어야하는데 B, C지역끼리만 연결되는 경우가 생기기 때문이였다. 그래서 BFS로 사다리가 없는 지역들을 구분하고, 구분된 지역에서 다른지역으로 갈 때 사다리를 최소로 놓도록 했다. 문제를 풀다보니 모든 지역을 잇기 위해 사다리를 놓는 비용의 합이 최소가 되어야 했기 때문에 이는 MST 문제와 같은 문제라는 것을 알았다. 그래서 가장 비용이 적게 드는 사다리를 놓은 다음에, 사다리를 놓아서 새롭게 갈 수 있는 지역이 생기면 그 지역에서 사.. 2024. 1. 18. [프로그래머스/C++] 카드 짝 맞추기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 카드 짝을 맞추는 최소 횟수를 구하면 되는 문제다. 그렇기 때문에 이동횟수가 최소가 되는 경우를 구하기 위해서는 BFS로 a에서 목적지까지 가는데 걸리는 입력 횟수가 최소가 되도록 계산하면 된다. 그리고 카드를 뒤집는 순서도 게임에 중요하다 예를 들면 a카드를 뒤집고 b카드를 뒤집는 경우와 b카드를 뒤집고 a카드를 뒤집는 경우가 최소 횟수가 다를 수 있다는 의미다. 그래서 카드의 순서에 대한 모든 경우를 구해 카드를 뒤집는 순서를 구하고, 그 순서에 따라 BFS로 최소 횟수를 구했다. 이후 모든 경우에 대해 입력이 최소가 되는 횟수를 return하면 된다. [아이디어 정리] 카드를 뒤집는 순서에 대한 .. 2024. 1. 16. [프로그래머스/C++] 아이템 줍기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 겹친 사각형으로는 캐릭터가 이동할 수 없다는게 핵심이다. 그래서 겹친 사각형의 경로를 없애주고, 없앤 다음 만들어진 경로를 BFS로 탐색하면 쉽게 풀리는 문제다. BFS로 탐색하는 것은 쉽지만, 어떤 경로를 이동할 수 있는지를 구하는게 생각보다 어려웠다. 처음에는 사각형의 좌표를 기준으로 겹쳐있는지를 보고 겹친 부분을 조건에 따라 삭제하려고 했다. 하지만 코드가 생각보다 길어질 것 같아서, 잘 생각해보니 겹칠 경우는 조건을 잡을 필요없이 겹친 부분을 0으로 없애면 실제로 가능한 경로만 남게 된다는 사실을 알았다. 그래서 하나의 사각형에서 이동이 가능한 경로를 그리고, 그 사각형의 경로 위에 다른 사.. 2024. 1. 11. [프로그래머스/Python] 미로 탈출 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 최소 횟수를 구해야 하므로 BFS로 Start지점에서 Lebber까지의 최소 횟수를 구하고, Lebber에서 Exit까지 다시 BFS로 최소 횟수를 구하면 되는 문제다. 즉, BFS를 두 번 써서 해결하면 된다. [요약] 1. Start지점을 찾고 Lebber 까지 걸리는 이동 횟수를 계산한다. 2. Lebber까지 이동이 가능하다면 Lebber부터 Exit까지 이동횟수를 계산한다. 3. 두 이동횟수를 더한 값을 리턴한다. HTML 삽입 미리보기할 수 없는 소스 dx = [0,0,1,-1] dy = [1,-1,0,0] defaultMap=[] defaultMap2=[] lenX=0 lenY=0 lebberX=-1 .. 2024. 1. 6. 이전 1 2 다음 반응형
