무인도 여행

링크텍스트

문제 설명

1. 상하좌우로 연결되어 있는 숫자를 더해서 return한다.

2. 연결된 곳이 없다면 -1 return
   
   

시행착오 및 문제 풀이

사실 이번 문제는 시행착오라 할 게 없었다 그저 오래 걸렸을 뿐....

상하좌우 보자마자 BFS를 떠올렸고 큐를 통해 문제 풀어야겠다! 생각함
그러나 늘 dfs랑 bfs는 어려워서 시간이 좀 걸림.. 생각도 많이 해야하고

정답 풀이

1. x의 상하좌우 이동, y의 상하좌우 이동, 방문 확인, 더할 숫자는 전역변수로 정의한다.

2. String 배열로 주어졌기 때문에 무인도 하나 당 숫자 or X를 하나씩 넣기 위해 char[][]으로 변환해준다.

3. 이중 for문을 통해 해당 칸이 숫자이고 아직 방문하지 않았다면 방문하여 상하좌우 확인해준다(bfs)
   3-1. 이때 한 무인도를 시작으로 bfs 해주고 오면 num은 초기화 해준다. (다른 무인도의 시작이므로)

4. 큐에 시작 무인도 인덱스 넣어주고 시작 무인도 방문처리 해준다. 큐가 비어있지 않을 때까지 반복해준다.
   4-1. 현재 무인도에서 상하좌우로 옮겨가며 범위를 벗어나지 않고, 이미 방문하지 않았고, X가 아니라면 거기서 다시 상하좌우로 검사해준다.
   그 후 큐에 다시 넣어서 현재 무인도 상하좌우가 끝나면 큐에 있는 무인도를 기점으로 다시 상하좌우 검사해준다.
   4-2. 위의 조건 중 하나라도 벗어난다면 그 무인도는 갈 수 없으므로 continue

5. 총 무인도의 갯수를 모르기 때문에 list형으로 선언해준 뒤 오름차순으로 넣어준다.
   5-1. 만약 list가 비어있다면(갈 수 있는 무인도가 없다는 뜻) -1 반환

정답 코드

//bfs
import java.util.*;
class Solution {
    static int[] move_x = {-1,1,0,0};
    static int[] move_y = {0,0,-1,1};
    //방문 확인
    static boolean[][] visited;
    static int num;
    
    public int[] solution(String[] maps) {

        //2차원 배열로 만들기
        char[][] map = new char[maps.length][maps[0].length()];
        for(int i=0; i<maps.length; i++) {
            for(int j=0; j<maps[0].length(); j++) {
                map[i][j] = maps[i].charAt(j);
            }
        }
        
        //방문 여부 체크
        visited = new boolean[map.length][map[0].length];
        
        //리스트
        ArrayList<Integer> list = new ArrayList<>();
        
        for(int i=0; i<map.length; i++) {
            for(int j=0; j<map[0].length; j++) {
                //다른 무인도 가면 숫자 초기화
                num = 0;
                
                //해당 칸이 숫자이고 방문하지 않은 곳이라면 bfs
                if(map[i][j] != 'X' && !visited[i][j]) {
                    bfs(map, i, j);
                }
                
                //주변에 더 이상 갈 곳이 없으면
                if(num != 0) {
                    list.add(num);
                }
            }
        }
        
        int[] answer = new int[list.size()];
        
        //갈 무인도가 없다면 -1
        if(list.size() == 0) {
            return new int[]{-1};
        }
        
        else {
            //오름차순 정렬
            Collections.sort(list);
            for(int i=0; i<list.size(); i++) {
                answer[i] = list.get(i);
            }
        }
    
        return answer;
    }
    
    public void bfs(char[][] map,int x, int y) {
        Queue<int[]> q = new LinkedList<int[]>();
        
        //시작 넣기
        q.offer(new int[]{x,y});
        
        //시작 방문 처리
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            //현재
            int[] temp = q.poll();
            int now_x = temp[0];
            int now_y = temp[1];
            
            num += map[now_x][now_y] - '0'; 
            
            for(int i=0; i<4; i++) {
                int next_x = now_x + move_x[i];
                int next_y = now_y + move_y[i];
                
                //범위를 벗어나거나 이미 방문을 했거나 X라면 무시
                if(next_x<0 || next_y<0 || next_x>=map.length || next_y>=map[0].length || visited[next_x][next_y] || map[next_x][next_y] == 'X') {
                    continue;
                }
                else {
                    q.offer(new int[]{next_x, next_y});
                    //방문 처리
                    visited[next_x][next_y] = true;
                }
            }
        }
    }
}

정답! 코드 너무 길어 징그러워

새롭게 알게된 점

char형을 Integer형으로 변환하려고 했다

num += Integer.valueOf(map[now_x][now_y]); 

하지만 이런식으로 작성하면 유니코드 값을 반환한다고 하네요
ex) 1 -> 49, 3 -> 51

이거는 구글링 도움을 받았습니다.

num += map[now_x][now_y] - '0'; 

해당 유니코드 값에서 '0'의 유니코드 값을 빼주면 int가 반환된다.
새로운 방식이다. 심지어 편해 애용하겠소.

---

옛날엔 dfs, bfs 너무 어려워서 손도 못댔는데 여러 번 푸니깐 그저 기계처럼 풀게 된다..