ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BOJ) 격자상의 경로
    알고리즘/백준 2021. 2. 4. 23:55
    반응형

    격자상의 경로

     

    10164번: 격자상의 경로

    입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으

    www.acmicpc.net

    N by M 행렬이 주어질 때, 격자 1번 칸에서 N*M 번 칸 까지 가는 모든 경로의 수를 구하는 문제다.

    또한, O 표시가 된 격자 번호가 하나가 주어지는데, 해당 격자를 무조건 들러야하는 경우의 수를 구해야 하는 문제이다.

     

    위의 조건을 생각하다가 한번에 1 -> N*M 까지 가는 것이 아니라, 1번 -> O 표시 격자 -> N*M 으로 가는 경우의 수를 구해주는 방법이 생각났다.우선, 좌표로 값을 저장하기 위해 격자의 번호를 좌표화했다.필요한 것은 중간에 O 표시된 격자의 좌표였다.여기서, O 표시된게 없는 경우 0으로 주어지기 때문에, 이 경우 가장 처음 시작점인 1번 격자칸을 임의로 O표시 해주었다.

     

    이렇게 O 표시된 격자 칸의 좌표가 구해졌으면, 1번 -> O 표시 번 , O 표시 번 -> N*M 번 까지 경로를 dp를 통해 구해주었다.

    여기서 중요한 점은 O 표시가 된 구간에서 합이 두 번 이루어졌다는 것이다.

    dp를 진행하면서 O번 ~ N*M 까지는 모든 값이 두 번 더해져있기 때문에 가장 마지막 격자칸으로 가는 경로의 수 / 2 를 해주어 답을 구했다.

     

     

    코드

     

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    public class GridPath_10164 {
      static final int[] dx = {0,-1}, dy = {-1,0};
    
      public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), mark = Integer.parseInt(st.nextToken());
    
        br.close();
        solution(n,m,mark);
      }
    
      private static void solution(int n, int m, int mark) {
        int[][] dp = new int[n+1][m+1];
        dp[0][1] =1;
        int[] markPos = getMarkedPosition(m,mark);
    
        setPathCount(dp, 1,1, markPos[0], markPos[1]);
        setPathCount(dp, markPos[0], markPos[1], n, m);
        System.out.println(dp[n][m]/2);
      }
    
      private static int[] getMarkedPosition(int m, int mark) {
        int divN = mark/m, divM = mark%m;
        if(isNoMarked(divN, divM)) {
          divM++;
        }
        if(divM ==0) {
          divM = m;
        } else {
          divN++;
        }
        return new int[] {divN, divM};
      }
    
      private static boolean isNoMarked(int divN, int divM) {
        return divN ==0 && divM ==0;
      }
    
      private static void setPathCount(int[][] dp, int startY, int startX, int n, int m) {
        for(int y=startY; y<=n; y++) {
          for(int x=startX; x<=m; x++) {
            for(int i=0; i<2; i++) {
              int nx = x + dx[i];
              int ny = y + dy[i];
              dp[y][x] += dp[ny][nx];
            }
          }
        }
      }
    }
    
    반응형

    '알고리즘 > 백준' 카테고리의 다른 글

    BOJ) 보석  (0) 2021.02.05
    BOJ) 멀티탭 스케줄링  (0) 2021.02.05
    BOJ) 캐슬 디펜스 (17135 번)  (0) 2021.02.03
    BOJ) 조합 (2407 번)  (0) 2021.02.03
    BOJ) 스택 수열 (1874 번)  (0) 2021.02.03

    댓글

Designed by Tistory.