Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Lv2
- Ainimation Blending
- Blend Type
- Object Pooling
- Unity
- 플레이어 방향전환
- ASTAR
- pccp 기출문제 1번
- Algorithm
- Hpbar
- heap tree
- Animation State Machine
- Hp바
- 충돌위험 찾기
- CSharp #자료구조
- raycasting
- 2D슈팅게임
- Back Tracking
- C#
- pccp 기출문제 3번
- 너비 우선 탐색
- 프로그래머스
- 유니티
- Scrooling
- Object Poling
- LayerMark
- 깊이 우선 탐색
- 플레이어 이동
- 오브젝트 풀링
- pccp 기출문제 2번
Archives
- Today
- Total
주녘공부일지
[프로그래머스 C#] Lv.3 아이템 줍기 본문
https://school.programmers.co.kr/learn/courses/30/lessons/87694
1. 정답코드 및 핵심 아이디어, 유의사항
다각형 범위의 테두리로만 이동할 수 있을 때, 목적지까지의 최소 이동 거리를 구하는 문제
1) 다각형의 테두리 구하기
- 구하려는 다각형의 테두리와 테두리 안쪽을 나타내는 2차원 int배열을 선언
-> 0 : 다각형 범위를 벗어난 영역 ( 이동 불가능 )
-> 1 : 다각형의 테두리 영역 ( 이동 가능 )
-> 2 : 다각형의 테두리 안쪽 영역 ( 이동 불가능 )
- 사각형 영역의 테두리 안쪽은 무조건 2로 세팅 ( 무조건 다각형의 테두리 안쪽이 됨 )
- 사각형 영역의 테두리는 다각형의 테두리 안쪽이 아니라면 다각형의 테두리가 됨
+ 만약 주어진 사각형 영역의 한 변의 길이가 1일 경우에 테두리가 아닌 테두리 안쪽을 지나갈 수 있게 되므로 모든 포지션 관련된 값을 2로 곱하여 길이가 1인 사각형의 테두리 안쪽을 표현할 수 있게 함
2) 최소 이동 거리 구하기
- BFS 알고리즘을 통해 최소 이동 거리 길찾기
https://godgjwnsgur7.tistory.com/47
주석 참조
using System;
using System.Collections.Generic;
public class Solution
{
// 좌표와 이동횟수를 담는 클래스
public class Pos
{
public int y;
public int x;
public int count;
public Pos(int y, int x, int count)
{
this.y = y;
this.x = x;
this.count = count;
}
}
public int solution(int[,] rectangle, int characterX, int characterY, int itemX, int itemY)
{
int answer = 0;
// 다각형의 테두리 1 (갈 수 있음), 다각형의 테두리 안쪽 2 (갈 수 없음)
var intArrays = new int[102, 102];
// 한 변의 길이가 1인 사각형에 대응하기 위해 모든 좌표를 *2로 둠
characterY *= 2;
characterX *= 2;
itemY *= 2;
itemX *= 2;
// 각 사각형 영역을 탐색해 다각형의 테두리와 내부를 구함
for (int i = 0; i < rectangle.GetLength(0); i++)
{
// 모든 좌표 * 2
int startPosY = rectangle[i, 1] * 2;
int startPosX = rectangle[i, 0] * 2;
int endPosY = rectangle[i, 3] * 2;
int endPosX = rectangle[i, 2] * 2;
// 현재 탐색하는 사각형의 영역 탐색
for (int y = startPosY; y <= endPosY; y++)
{
for (int x = startPosX; x <= endPosX; x++)
{
// 테두리인 경우
if (y == startPosY || y == endPosY || x == startPosX || x == endPosX)
{
// 다른 사각형의 테두리 안쪽이 아닌 경우에만 갈 수 있는 길로 체크
if (intArrays[y, x] != 2)
{
intArrays[y, x] = 1;
continue;
}
}
// 테두리 안쪽인 경우
intArrays[y, x] = 2;
}
}
}
var queue = new Queue<Pos>();
var dirY = new int[4] { 0, 0, 1, -1 };
var dirX = new int[4] { 1, -1, 0, 0 };
queue.Enqueue(new Pos(characterY, characterX, 0));
// BFS 탐색
while (queue.Count > 0)
{
Pos currPos = queue.Dequeue();
intArrays[currPos.y, currPos.x] = 2; // 방문처리
for (int i = 0; i < 4; i++)
{
// 범위를 벗어날 수 없으므로 예외처리하지 않음 (0,0 ~ 101,101)
Pos movePos = new Pos(currPos.y + dirY[i], currPos.x + dirX[i], currPos.count + 1);
// 목표 지점에 도착
if (movePos.y == itemY && movePos.x == itemX)
{
// 모든 좌표 * 2 였기 때문에 이동 횟수 / 2
answer = movePos.count / 2;
queue.Clear();
break;
}
if (intArrays[movePos.y, movePos.x] == 1)
queue.Enqueue(movePos);
}
}
return answer;
}
}
'CodingTest > Programmers Lv.3' 카테고리의 다른 글
[프로그래머스 C#] Lv.3 / 2차원 동전 뒤집기 (1) | 2024.02.28 |
---|---|
[프로그래머스 C#] Lv.3 부대 복귀 (1) | 2024.02.24 |
[프로그래머스 C#] Lv.3 등대 (0) | 2024.02.19 |
[프로그래머스 C#] Lv.3 110 옮기기 (0) | 2024.02.18 |
[프로그래머스 C#] Lv.3 순위 (0) | 2024.02.07 |