[프로그래머스 Level 2] 게임 맵 최단거리

🖊️ 문제 게임 맵 최단거리 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫..

• format_list_bulleted Algorithm/프로그래머스 : Level 2
• · 2021. 11. 15.
• textsms

[Algorithm] 다익스트라 알고리즘 : 음수 간선이 있으면 안 되는 이유

인트로 [2021.11.15 오타 수정] [2022.08.16 오류 수정] 다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘이다. 단 가중치가 모두 양수라는 조건이 있다. 이러한 이유는 다익스트라 알고리즘은 그리디(Greedy) 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다. 반면 음수 가중치가 포함된 그래프라면 벨만-포드 알고리즘 사용 시 목표 노드까지의 최단 경로를 구할 수 있다. 그렇다면 음수가 포함된 가중치에서 다익스트라 알고리즘을 사용하면 어떤 문제가 발생할까? - - 음수 가중치가 포함된 그래프에서 다익스트라 알고리즘의 문제점을 파악하면 벨만-포드 알고리즘을 더 쉽게 이해할 수 있을 것이다. 다익스트라 문제점 :..

• format_list_bulleted Algorithm/탐색
• · 2021. 10. 12.
• textsms

[코딩 팁] 방향 배열(Direction Array) : 상하좌우 이동

인트로 2차원 좌표상에서 한 점을 기준으로 상하좌우 좌표를 구할 때 코드를 간결하게 작성하는 방법이다. 방향 배열은 BFS, 다익스트라, A*알고리즘에 자주 등장한다. 코드 switch 혹은 if-else문을 작성하지 않아도 된다. int main() { //상 하 좌 우 int dirY[4] = { -1, 1, 0, 0 }; int dirX[4] = { 0, 0, -1, 1 }; int arr[3][3] = { {1,2,3},{4,5,6}, {7,8,9} }; int posY = 1, posX = 1; cout

• format_list_bulleted Algorithm/감명 깊게 본 코딩 팁
• · 2021. 10. 3.
• textsms