https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
- 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
- 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
(풀이코드)
import java.util.*;
class root{
int r;
int c;
int cnt ;
public root(int r, int c,int cnt) {
this.r = r;
this.c = c;
this.cnt = cnt;
}
}
class Solution {
public int solution(int[][] maps) {
int n = maps.length,m=maps[0].length;
int answer = n*m+1;
Queue<root> q = new LinkedList<root>();
boolean[][] v = new boolean[n][m];
for(int i = 0; i< n; i++) {
for(int j = 0; j<m; j++) {
v[i][j]= maps[i][j]==1?false:true;
}
}
v[0][0]=true;
q.offer(new root(0,0,1));
while(!q.isEmpty()) {
root R = q.poll();
v[R.r][R.c]=true;
if(R.r==n-1 && R.c==m-1) {
answer = R.cnt;
break;
}
// 방향은 하 - 우 - 상 - 좌
if(R.r<n-1&&!v[R.r+1][R.c]) {
v[R.r+1][R.c]=true;
q.offer(new root(R.r+1,R.c,R.cnt+1));
}
if(R.c<m-1&& !v[R.r][R.c+1]) {
v[R.r][R.c+1]=true;
q.offer(new root(R.r,R.c+1, R.cnt+1));
}
if(R.r>0 && !v[R.r-1][R.c]) {
v[R.r-1][R.c]=true;
q.offer(new root(R.r-1,R.c, R.cnt+1));
}
if(R.c>0 && !v[R.r][R.c-1]) {
v[R.r][R.c-1]=true;
q.offer(new root(R.r,R.c-1, R.cnt+1));
}
}
return answer==(n*m+1)?-1:answer;
}
}
(코드풀이)
이 문제는 효율성까지 있어서 여러가지로 고민을 많이 한 문제이다.
우선 최단거리 == BFS 라는 공식에 따라 BFS로 문제를 풀었다.
먼저 1.1에서 마지막 지점인 n,m까지 가는 현재 위치와 몇번 칸을 지나왔는지를 표현해줄 root를 선언해준다.
이 값을 queue에 넣고 BFS를 돌도록 한다.
그리고 이제 main함수로 들어간다.
값의 비교를 위해서 우선 n값, m값으로 전체 배열의 크기를 확인한다.
모든 점을 거쳐 최대로 도착하는 게 n*m의 값이니 answer는 불가능한 n*m+1로 해준다. 사실 Integer.MAX_VALUE를 해주는게 너 편했을 듯 한다.
그리고 나서 BFS를 돌 Queue를 선언해 준다.
그리고 갈 수 있는 길인지를 표현해 줄 boolean [][] v(visitied)를 선언해준다.
그리고 주어진 boolean[][] v 값에서 벽으로 된 부분을 제외하기 위해서 1,1~n.m까지 반복하면서 maps[i][j]의 값이 1이면 방문 가능하니 false, 0이면 방물 불가 == 이미 지나온 길 이라는 의미로 true로 표시한다.
그리고 나서 BFS를 돌기 위한 첫번쨰 값을 넣어준다. 맨 처음 값으로 0,0에서 시작하며 cnt는 칸수 1을 의미한다.
그리고 q가 모두 없어지기 전까지 while반복문을 통해 이동한다.
우선 root R을 하나 꺼내온다.
그리고 나서
혹시 도착한 값이 n,m의 끝일 수 있으니 먼저 반복문을 꺠고 나올 수 있는 선언을 먼저 해준다.
그리고 1~n, 1~m으로 가야 길이 나오기 떄문에 // 하-우-상- 좌 순서로 이동할 수 있는지 없는 지를 검사하고, 이동가능하다면, 그 값으로 도착하기 위한 최단거리 값이므로, v[R.r+?]][R.c+?]에 true로 만들어 주고, cnt에는 +1을해서 검사해준다.
이 부분이 하 // 아래로 가는 경우를 표현한 코드이다.
그리고 뒤의 값들은 우, 상, 좌 를 각각 나누어 썼다.
그리러면 아까 나왔던 break조건에 따른 answer값이 정해지는데, 아까 선언했던 최대값과 동일하다면 변동이 없었던 것으로 빠져나갈 수 없다는 의미로 -1을 return 하고, 아니라면 최단 거리의 값인 answer를 retrun 하게 된다.
// 여러 시행착오들이 있었다. v로 표현된 visited에 관한건데,
// 이미 그 값을 이전에 지나 갔다는 것은 그 지점까지의 최단거리로 올 수 있는 방법을 지났다고 생각하면된다.
// 그래서 맨 처음에는 Queue에 넣는 root에 visited의 boolean[][]배열까지 넣어서 탐색을 하다 계속 타임에러가 났다.
// 그리고 나서는 검사를 위해서는 Queue에서 빠저나온 뒤에 visited를 처리해 주는게 좋다고 생각하여 q.poll이후에 visitied를 처리해주니 또 timeout이 떴다..그 거리까지 도착할 수 있었다는건 최단거리라는 걸 이미 말해주므로 그냥 boolean[][] v 배열 하나로 처리 할 수 있는 상황이었다. // 다음에도 여기까지 도착하는 방법 중 최단인가를 다시 한번 생각해 봐야 겠다.