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 | 31 |
Tags
- 기업분석
- 자바
- 잉여현금흐름
- 접근제어자
- 현금흐름표
- 인플레이션
- S&P500
- 제태크
- 무디스
- Java
- 객체지향
- object
- 알고리즘
- mco
- 주식
- etf
- 금리인하
- 미국주식
- 금리인상
- javascript
- 다형성
- FCF
- 주린이
- 백준
- XLF
- 배당성장
- 프로그래머스
- 오버라이딩
- 그리디 알고리즘
- StringBuffer
Archives
- Today
- Total
오늘의하루
[프로그래머스 2단계 - JAVA] 게임 맵 최단거리 본문
문제
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
풀이
import java.util.*;
class Solution {
public int solution(int[][] maps) {
int answer = -1;
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
boolean[][] vistied = new boolean[maps.length][maps[0].length];
int[][] check = new int[maps.length][maps[0].length];
for(int i = 0; i < check.length; i++){
System.arraycopy(maps[i],0,check[i],0,check[0].length);
}
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0,0});
vistied[0][0] = true;
while(!q.isEmpty()){
int[] now = q.poll();
for(int i = 0; i < 4; i++){
int nextX = now[0] + dx[i];
int nextY = now[1] + dy[i];
if(nextX < 0 || nextY < 0 || nextX >= maps.length || nextY >= maps[0].length){
continue;
}
if(vistied[nextX][nextY] || maps[nextX][nextY] == 0){
continue;
}
q.offer(new int[]{nextX, nextY});
vistied[nextX][nextY] = true;
check[nextX][nextY] = check[now[0]][now[1]] + 1;
}
}
if(check[maps.length - 1][maps[0].length -1] == 1){
return answer;
}else{
answer = check[maps.length -1][maps[0].length -1];
return answer;
}
}
}
- BFS를 이용해서 푼다.
'JAVA' 카테고리의 다른 글
[자바의 정석] 객체지향 언어 & 클래스와 객체 (0) | 2022.10.12 |
---|---|
[Java] 자바의 정석 객체지향 part 복습 (1) | 2022.09.30 |
[프로그래머스 1단계 - JAVA] 하샤드 수 (1) | 2022.09.16 |
[프로그래머스 1단계 - JAVA] 정수 내림차순으로 배치하기 (0) | 2022.09.16 |
[프로그래머스 1단계 - JAVA] 문자열 내 p와 y의 개수 (0) | 2022.09.16 |
Comments