눈물의 문제풀이
문제를 처음 봤을 때 50x50x170의 직사각형 상자에 갇힌 기분이었다.
도대체 이게 뭔 소릴까...
이제 그래프를 막 배우고 dfs와 bfs의 개념정리도 제대로 되어있지 않은 상태로
이 문제를 풀려니 너무 어려웠다.
애초에 왜 bfs를 쓰는가에 대하여도 이해를 못하고 있었다.
테스트에 좌표문제는 필수인 것 같은데 좌표만 보면 덜덜 떨린다....
그래서 이 문제를 잡고 몇시간을 고민하면서 진짜 눈물흘릴 뻔했다..
내 스스로 머리가 안돌아가는 느낌도 괴로웠지만,
'정말 아무것도 모르겠다!'
이 생각밖에 안들었다.
고민해서 해결되지 않을 것 같아서 최고의 선생님, 구글을 찾았다...
일단 보고 분석하고 백지에서 다시 써보자는 마음으로.
가보자고~!
문제는 이러하다.
문제 설명
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) 위치에 있습니다.
입출력 예시
브레인스토밍
무엇부터 해야할지 모르겠는 상황에서 스터디장님의 도움을 받아 우선 dfs를 쓸 것인가 bfs를 쓸 것인가 구분지었다.
DFS 그게 뭔데?
- 깊이 우선 탐색법
- 모든 분기의 끝을 탐색하기 때문에
- 순열이나 어떠한 모든 경우의 수를 알아내기 위할 때 사용
- 정점 노드를 기점으로
BFS 너는 뭔데?
- 너비우선 탐색법
- 트리구조로 치자면 레벨별 탐색
- 해당 목적지가 존재하는 레벨을 탐색하는 방법
- 거리 계산 프로그램에 적합
그러니까, 여기서 깊이 우선으로 탐색해버리면 모든 경우의 수를 탐색하기 때문에 적절치 못하고
너비 우선 탐색을 하면 모든 분기의 엣지들을 다 훑는 것이 아니라 필요한 정보가 있는 레벨을 탐색하게 되는 것이다.
지금도 쓰면서 약간 헷갈려 하는 중이다...
암튼 그렇게 방향성을 잡고 코드를 짜보았다.
package findShortestWay;
//프로그래머스 게임맵최단거리 구하기 ROR
import java.util.LinkedList;
import java.util.Queue;
class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {-1, 1, 0, 0};
public int soulution(int[][] maps){
int answer = 0;
int[][] visited = new int[maps.length][maps[0].length];
visited[0][0] = 1; //시작위치 방문체크
//bfs 탐색
bfs(maps, visited);
//도착지 값을 넣어주기
answer = visited[maps.length - 1][maps[0].length - 1];
//갈 수 없다면 -1 return
if (answer == 0){
answer = -1;
}
return answer;
}
public void bfs(int[][] maps, int[][] visited){
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{0, 0});
while (!q.isEmpty()){
int[] now = q.poll();
int x = now[0]; //0
int y = now[1]; //0
//4방 탐색
for (int i = 0; i < 4; i++) {
//이동시 위치
int nx = x + dx[i]; //0
int ny = y + dy[i]; //0
//범위 벗어나는지 확인
//방문했는지 확인
//갈 수 있는지 확인
if(nx >= 0 && nx < maps.length && ny >=0 && ny < maps[0].length && visited[nx][ny] == 0 && maps[nx][ny] == 1){
//방문했다고 체크하기
visited[nx][ny] = visited[x][y] + 1;
//큐에 넣기
q.add(new int[]{nx, ny});
}
}
}
}
}
- 처음 정수배열 dx dy는 이동하는 방향에 대해 정의하기 위해 선언해놓았다.
- 아래 메서드 bfs에서 4방탐색 아래를 보면 포문으로 4번 돌려 갈 수 있는 방향을 알 수 있고,
- 출발점, 즉 (x, y) 에 이 dx, dy의 값을 각각 더하여 현재 위치를 다시 설정하는 것이다.
- 그런데 문제에서 이 맵밖을 나갈 수 없다는 조건이 있어서 만약 x나 y중에 음수가 있으면 이는 맵 탈출이라고 본다.
따라서 이 경우에는 q에 add되지 않고 패스된다.- 이런 과정을 반복해서 q에 아무것도 남아있지 않게 되면,
if문의 실행결과에 따라 내가 방문했던 좌표들은 visited[][] = 0에서 이동 횟수만큼 +1을 하게 된다.- 그리고 다시 solution메서드로 돌아와서 만약 목표로 하는 (n-1, m-1)에 방문한 적이 없었다면
그 좌표에 대한 visited는 0이 되고 이때는 갈 수 없은 경우로 판단, -1을 return하게 되는 것이다.
이 문제를 완벽하게 이해하기 위해서는 아무래도 백지에 한 다섯번 정도 더 반복해서 구현해보아야 할 것 같다.
아직 bfs나 dfs나 익숙하지가 않아서 많이 어려웠다....(주륵)
코드 자체를 분석하는 데에만 몇시간을 쏟았던 것 같다....
뭔가 오롯이 내 스스로의 힘으로 해결해야 할 것 같은 느낌에 검색하고 이런거에 거부감이 좀 들었는데
스터디장님 말씀이, 현업에서는 모르면 모른다고 빨리 말을 해야 한다고.
프로젝트 하루전에 "모르겠어요~" 이러면 더 욕나오는 일이라고 하셨다.
필요할 때에는 적절히 검색을 이용하자.
아직 나는 개발초보자이기 때문에, 자바의 기본 문법도 100프로 다 안다고 할 수 없기에 ㅋㅋㅋ.....
그리고, 스터디는 진짜 일주일 공부 일정 중 가장 유익한 것 같다.
화이팅~~!!
하하 재밌어요 : D