[TIL] 2월 26일

이코테 탐색 알고리즘 음료수 얼려먹기 149p

문제를 보고 DFS를 써야할지 BFS를 써야할지도 모르겠고 문제에 어떻게 접근해야할지도 모르겠어서 강의에 나온 해설을 보고, 자바 코드를 훔쳐보면서 문제를 풀었다.

public class Ice {
    public static int n;
    public static int m;
    public static int[][] graph = new int[1001][1001];

    // DFS로 연결된 노드 모드 방문
    public static boolean dfs(int x, int y) {
        // 범위 벗어나면 false 반환
        if (x < 0 || y < 0 || x > n - 1 || y > m - 1) {
            return false;
        }

        // 방문하지 않은 노드 방문처리하고 상하좌우 재귀적으로 호출
        if (graph[x][y] == 0) {
            graph[x][y] = 1;
            dfs(x, y - 1);
            dfs(x, y + 1);
            dfs(x - 1, y);
            dfs(x + 1, y);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for (int i = 0; i < n; i++) {
            sc.nextLine();
            for (int j = 0; j < m; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // dfs 수행할때마다 result 증가
        int result = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(dfs(i,j)){
                    result++;
                }
            }
        }
        System.out.println(result);
    }
}

• graph에 요소를 입력받을때 sc.nextInt()로 해주니깐 입력받는 숫자마다 공백을 넣어줘야한다.

  • 나동빈님이 하신거처럼 String으로 한줄씩 받아서 숫자로 변환하는 방법에 익숙해져보자.

    for (int i = 0; i < n; i++) {
    		String str = sc.nextLine();
    		for (int j = 0; j < m; j++) {
    				graph[i][j] = str.charAt(j) - '0';
    		}
    }

오늘 한일

• 미션5 피드백 받았는데 점수구하는 부분의 전체적인 로직을 바꿔야할거같다고 하셨다. 위치를 관리하는 Position 클래스를 추가해주고, Piece에서 Position을 갖도록 바꾸고 점수구하는 메소드도 리뷰어가 제안해주신대로 구현했다. 문제는 같은 세로줄에 있는 폰 구하기ㅠㅠ 이걸로 계속 헤매고 있다.
• 이코테 DFS예제문제 하나 풀었다. 풀었다기 보다는 문제접근방식을 전혀 모르겠어서 해설영상을 보고 공부했다.

Todo

(내일)

• 개구리책
• collect()
• 미션5 수정