[백준] 5573 산책 (플레3)

9/19
https://www.acmicpc.net/problem/5573

import java.util.*;
import java.io.*;
public class Main {
    static int h,w,n;
    static int[][] map;
    static int[] ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new int[h+1][w+1];

        for(int i=0;i<h;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<w;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 0이면 아래쪽, 1이면 오른쪽으로 이동하고
        // 값 뒤집기; 0,1
        for(int i=0;i<n-1;i++){
            // System.out.println(i+":");
            ans = walk();
        }
        for(int a:ans)
            System.out.print(a+" ");
    }

    static int[] walk(){
        int x=0; int y=0;
        while(true){
            if(x>h || y>w){
                // for(int i=0;i<h;i++){
                //     for(int j=0;j<w;j++){
                //         System.out.print(map[i][j]+" ");
                //     }
                //     System.out.println();
                // }

                // System.out.println(x+", "+y);
                return new int[]{x,y};
            }

            if(map[x][y]==1){
                map[x][y] = 0;
                x=x+1;
            }else if(map[x][y]==0){
                map[x][y] = 1;
                y=y+1;
            }
        }
    }
}

=> 시간 줄이기; O(hwn) -> n 줄이기; 위상 정렬

import java.util.*;
import java.io.*;
public class Main {
    static int h,w,n;
    static int[][] map, dis;
    static int[] ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()); 
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        map = new int[h+1][w+1];
        dis = new int[h+1][w+1];
        dis[0][0]=n;

        for(int i=0;i<h;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<w;j++){
                map[i][j] = Integer.parseInt(st.nextToken());

                if(dis[i][j]%2 == 0){
                    dis[i+1][j] += dis[i][j]/2;
                    dis[i][j+1] += dis[i][j]/2;
                }else{
                    if(map[i][j] == 1){
                        dis[i][j+1] += dis[i][j]/2 + 1;
                        dis[i+1][j] += dis[i][j]/2;
                    } else{
                        dis[i+1][j] += dis[i][j]/2 + 1;
                        dis[i][j+1] += dis[i][j]/2;
                    }
                }
            }
        }

        ans = walk();
        
        for(int a:ans)
            System.out.print(a+" ");
    }

    static int[] walk(){
        int x=0; int y=0;
        while(true){
            // System.out.println(x+", "+y);
            if(x>h || y>w){
                // System.out.println(x+", "+y);
                return new int[]{x,y};
            }

            if(dis[x][y]%2 == 0){
                // System.out.println("change");
                //값 변경
                if(map[x][y]==1){
                    x=x+1;
                }else if(map[x][y]==0){
                    y=y+1;
                }
            }else{
                //원래 값
                if(map[x][y]==1){
                    y=y+1; // 오른쪽
                    
                }else if(map[x][y]==0){
                    x=x+1; // 아래
                }
            }
            
        }
    }
}

=> 틀림
n번째로 결정하는 것이 아니라 n-1번째로 해서 값 계산해서 결과값 내기

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

public class Main {
    static int H, W, N;
    static int[][] arr = new int[1002][1002];
    static int[][] dp = new int[1002][1002];

    static void dfs(int y, int x) {
        if (y > H || x > W) {
            System.out.println(y + " " + x);
            return;
        }
        if (arr[y][x] == 0) {
            dfs(y + 1, x);
        } else {
            dfs(y, x + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= H; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= W; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[1][1] = N - 1;

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                int temp = dp[i][j];
                if (arr[i][j] == 1) {
                    dp[i][j + 1] += temp / 2;
                    dp[i + 1][j] += temp / 2;
                    if (temp % 2 == 1) dp[i][j + 1]++;
                } else {
                    dp[i][j + 1] += temp / 2;
                    dp[i + 1][j] += temp / 2;
                    if (temp % 2 == 1) dp[i + 1][j]++;
                }
            }
        }

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if (dp[i][j] % 2 == 1) {
                    arr[i][j] = (arr[i][j] + 1) % 2;
                }
            }
        }

        dfs(1, 1);
    }
}