[코드트리 챌린지] 체크판 위에서2

코드트리 블로그 챌린지 1주차 리뷰 글입니다

 

실력진단은 지난번에 봤던 결과인데, 블로그 챌린지 기간동안 공부하고 어떻게 변화하는 지 후기 남기도록 하겠습니다!

 

저는 기업별 커리큘럼을 신청하였고 오늘은 네이버 커리큘럼을 풀고 있습니다

체크판 위에서 2 문제를 리뷰해보고자 합니다

https://www.codetree.ai/cote/14/problems/on-the-checkboard-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

풀이방법

• 시작점 0,0 -> 도착점 R, C로 가는데, 무조건 오른쪽,아래로 점프
• 같은 색이 아닌 위치로만 점프 가능
• 2번의 점프 이후 도착점으로 점프 할 수 있는 경우의 수를 센다

import java.util.*;
import java.io.*;

public class Main {
    public static char[][] map;
    public static int row, col, res;
    public static void main(String[] args) throws IOException {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map =new char[row][col];
        for(int i=0; i<row; i++) {
            map[i] = String.join("", br.readLine().split(" ")).toCharArray();
        }
        dfs(0, 0, 0, map[0][0]);
        System.out.println(res);
        br.close();
    }

    public static void dfs(int r, int c, int cnt, char prev) {
        if(cnt == 2) {
            // 점프해서 도착지점에 갈 수 있는지
            if(r<row-1 && c<col-1 && map[row-1][col-1] != prev) res++;
            return;
        }

        for(int i=r+1; i<row; i++) {
            for(int j=c+1; j<col; j++) {
                if(map[i][j] != prev) {
                    dfs(i, j, cnt+1, map[i][j]);
                }
            }
        }
    }
}