[틀림] 백준 20165 도미노장인 // dfs, 구현

https://www.acmicpc.net/problem/20165

* 시도1

table을 2개 놓고 dfs?

k칸을 어떻게 처리?

배열에 k만큼 넘어졌다고 표시하면?

if(dir=='E'){
    for(int i=0;i<arr[y][x];++i){
      if(arr[y][x+i] > 0){
          cnt++;
        arr[y][x+i]=0;
    }
}

문제 : 다음에 언제 멈출지 계산하기가 매우 복잡해짐, dfs는 한칸씩 보는건데 이러면 다음상태에 영향을 끼쳐버림.

실제로 멈춰야되는데 진행이 되는 문제 발생

* 풀이

일단 배열을 원본, 백업으로구분

삭제된것 : 원본에 높이를 0으로 둠

remain이라는 상태 추가

remain이 0이되면, 정답갱신, 리턴

remain은 계속 MAX로 갱신필요. (내가더 큰경우 vs 엄청큰게 나오는경우)

remian을 직전값 vs 새값 비교로 계속 갱신해줘야함.

 

정답코드

while문으로 풀수도 있음. (attack 함수)

import java.util.*;

public class Main {

    static int ret,n,m,r;
    static int[][] arr = new int[104][104];
    static int[][] backup = new int[104][104];
    static boolean[][] vis = new boolean[104][104];

    //remain : 넘어져야할 도미노의 갯수
    //cnt : 넘어뜨린 도미노의 수
    static void dfs(int y, int x, char dir, int cnt, int remain){
//        System.out.println(y+" "+x+" "+dir+" "+cnt+" "+remain);
        if(y<=0 || x<=0 || y>n || x>m){
            ret+=cnt;
            return;
        }
//        if(arr[y][x] == 0 ){
//            return;
//        }
        if(remain ==0){
            ret+=cnt; //이때도 갱신필요!
            return;
        }

        remain = Math.max(remain-1,arr[y][x]-1);

        if(arr[y][x]>0){
            cnt++;
            arr[y][x]=0;
        }

        if(dir=='E'){
//            for(int i=0;i<arr[y][x];++i){
//                if(arr[y][x+i] > 0){
//                    cnt++;
//                    arr[y][x+i]=0;
//                }
//            }

            dfs(y,x+1,dir,cnt, remain);

        }
        else if(dir=='N'){
//            for(int i=0;i<arr[y][x];++i){
//                if(arr2[y-i][x]=='S'){
//                    cnt++;
//                    arr2[y-i][x]='F';
//                }
//            }
            dfs(y-1,x,dir,cnt,remain);

        }
        else if(dir=='W'){
//            for(int i=0;i<arr[y][x];++i){
//                if(arr2[y][x-i]=='S'){
//                    cnt++;
//                    arr2[y][x-i]='F';
//                }
//            }
            dfs(y,x-1,dir,cnt,remain);
        }
        else if(dir=='S'){
//            for(int i=0;i<arr[y][x];++i){
//                if(arr2[y+i][x]=='S'){
//                    cnt++;
//                    arr2[y+i][x]='F';
//                }
//            }
            dfs(y+1,x,dir,cnt,remain);
        }
    }

    static void attack(int y, int x, char dir){
        if(arr[y][x]==0){
            return;
        }

        int dy=0,dx=0;
        if(dir=='E') dx=1;
        else if(dir=='W') dx=-1;
        else if(dir=='N') dy=-1;
        else if(dir=='S') dy=1;

        int cnt = arr[y][x]; // 넘어뜨릴수 있는 도미노 갯수
        while(true){
            if(x<=0 || y<=0 || y>n || x>m) break;
            if(cnt<1) break;

            System.out.println(y+" "+x+" "+cnt);

            cnt = Math.max(cnt-1,arr[y][x]-1);

            if(arr[y][x]>0) ret++;
            arr[y][x]=0; //넘어뜨리기
            x+=dx;
            y+=dy;
        }
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        r = sc.nextInt();
        for(int i=1;i<=n;++i){ //1-idx
            for(int j=1;j<=m;++j){
                int tmp = sc.nextInt();
                arr[i][j]=tmp;
                backup[i][j]=tmp;
            }
        }

        for(int i=0;i<r;++i){
            int y1 = sc.nextInt();
            int x1 = sc.nextInt();
            char c = sc.next().charAt(0);
            int y2 = sc.nextInt();
            int x2 = sc.nextInt();

//            attack(y1,x1,c);
            dfs(y1,x1,c,0,arr[y1][x1]);

            arr[y2][x2]= backup[y2][x2]; //세우기
        }
        System.out.println(ret);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                if(arr[i][j]>0){
                    System.out.print("S ");
                }
                else{
                    System.out.print("F ");
                }
            }
            System.out.println();
        }
    }
}