반응형 BFS17 [프로그래머스/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 다음 반응형
