-
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