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

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

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

[프로그래머스 Level 2] 거리두기 확인하기 (2021 카카오 기출)

🖊️ 문제 거리두기 확인하기 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어, 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 ..

• format_list_bulleted Algorithm/프로그래머스 : Level 2
• · 2021. 11. 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

[Algorithm] A* 알고리즘 : 최단 경로 탐색

✍️ 인트로 A* 알고리즘은 그래프의 탐색 알고리즘으로 주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다. 대표적인 그래프 탐색 알고리즘들과 A*의 차이점은 BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며 다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다. 반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다. [※ 정리 ※] BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘 A* : 가중치 그래프, 시작..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 3.
• textsms

[C#] 미로 만들기와 길 찾기 알고리즘 Part 3 : BFS 길 찾기

인트로 C# 콘솔 프로그래밍으로 미로를 만들고 BFS, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다. Part3에선 BFS, A* 길 찾기 알고리즘으로 미로의 출구를 찾으려 한다. 본 포스팅에선 BFS를 사용해 출구를 찾는다. BFS를 알고 싶다면? [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 인트로 그래프의 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색)를 구현해보려 한다. DFS와 다르게 BFS는 주로 한 가지 목적으로 사용된다. 그것은 가중치가 없는 그래프의 최단 경로를 구할 kangworld.tisto..

• format_list_bulleted C#
• · 2021. 8. 31.
• textsms

[C#] 미로 만들기와 길찾기 알고리즘 Part 2 : Player 만들기

인트로 C# 콘솔 프로그래밍으로 미로를 만들고 BFS, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다. Part2에선 플레이어를 미로에 추가하려 한다. (+ Visual Studio 기준으로 포스팅을 이어나갈 예정입니다.) Player 클래스 추가 화면에 미로를 Render 하는 것은 Board의 기능이다. 그렇다면 Player 위치를 Board가 어떻게든 알고 있는 상태에서 Render시 플레이어 위치를 다른 색으로 표시하면 된다. 더보기 class Board { ... Player _player; ... public void InitializeBoard(int size, Player player) { ... _player = player; ... } } class Program { s..

• format_list_bulleted C#
• · 2021. 8. 30.
• textsms