1005 알고리즘 공부 기록

SWEA 1949 등산로 조성

첫번째 시도한 풀이 방법 :
n*n돌면서 각칸 k만큼 깎기 ->가장 높은 봉우리 찾기 -> 낮은곳으로 dfs

틀린 이유 :
1. 문제를 잘못읽음 -> 처음 입력에서 가장 높은 봉우리가 시작점이여야한다(문제가 설명이 좀 부족했던듯)
2. 문제를 잘못읽음 -> 최대 k만큼 깍는거라서 1부터 k만큼깎는 경우를 다 고려해야한다.

(49/51) 틀린코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class pos2 {
	int x;
	int y;
	int dep;

	pos2(int x, int y, int dep) {
		this.x = x;
		this.y = y;
		this.dep = dep;
	}
}

public class swea194 {
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int n, k;
	static int[][] arr;
	static int MAX;
	static Queue<pos2> q;
	static boolean[][] visited;
	static int max = 0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		for (int o = 1; o <= t; o++) {
			max = 0;
			int cnt=0;
			n = scan.nextInt();
			k = scan.nextInt();
			arr = new int[n][n];
			MAX = 0;
			ArrayList<pos2> list = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					arr[i][j] = scan.nextInt();
					if (arr[i][j] >= MAX) {
						MAX = arr[i][j];
						cnt++;
					}
				}
			}
			// 깎기
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					arr[i][j] -= k;
					for (int a = 0; a < n; a++) {
						for (int b = 0; b < n; b++) {
							if (arr[a][b] == MAX) {	//시작점
								visited=new boolean[n][n];
	                            visited[a][b]=true;
								dfs(a,b,0);
							}
						}
					}
					arr[i][j]+=k;//원상복구
				}
			}
            System.out.println("#"+o+" "+(max+1));

			
		}

	}

    public static void dfs(int i,int j,int depth) {

            for(int a=0;a<4;a++) {
                int nx=i+dx[a];
                int ny=j+dy[a];
                if(nx>=0&&ny>=0&&nx<n&&ny<n&&!visited[nx][ny]) {
                    if(arr[nx][ny]<arr[i][j]) {
                        if(max<depth+1) {
                            max=depth+1;
                        }
//                        System.out.println(arr[nx][ny]+" "+(depth));
                        visited[nx][ny]=true;
                        dfs(nx,ny,depth+1);
                        visited[nx][ny]=false;
                    }
                }
            }   
           
    }

}

정답 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class pos2 {
	int x;
	int y;
	int dep;

	pos2(int x, int y, int dep) {
		this.x = x;
		this.y = y;
		this.dep = dep;
	}
}

public class swea194 {
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	static int n, k;
	static int[][] arr;
	static int MAX;
	static Queue<pos2> q;
	static boolean[][] visited;
	static int max = 0;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		int t = scan.nextInt();
		for (int o = 1; o <= t; o++) {
			max = 0;
			int cnt=0;
			n = scan.nextInt();
			k = scan.nextInt();
			arr = new int[n][n];
			MAX = 0;
			ArrayList<pos2> list = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					arr[i][j] = scan.nextInt();
					if (arr[i][j] >= MAX) {
						MAX = arr[i][j];
						cnt++;
					}
				}
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(arr[i][j]==MAX) {
						list.add(new pos2(i,j,0));
					}
				}
			}
			// 깎기
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					for(int m=1;m<=k;m++) {
						arr[i][j] -= m;
						
						for(int a=0;a<list.size();a++) {
							
							pos2 pos =list.get(a);
							if(pos.x==i&&pos.y==j)continue;
							visited=new boolean[n][n];
	                        visited[pos.x][pos.y]=true;
							dfs(pos.x,pos.y,0);
						}
						arr[i][j]+=m;//원상복구
					}
					
				}
			}
            System.out.println("#"+o+" "+(max+1));

			
		}

	}

    public static void dfs(int i,int j,int depth) {

            for(int a=0;a<4;a++) {
                int nx=i+dx[a];
                int ny=j+dy[a];
                if(nx>=0&&ny>=0&&nx<n&&ny<n&&!visited[nx][ny]) {
                    if(arr[nx][ny]<arr[i][j]) {
                        if(max<depth+1) {
                            max=depth+1;
                        }
                        visited[nx][ny]=true;
                        dfs(nx,ny,depth+1);
                        visited[nx][ny]=false;
                    }
                }
            }   
           
    }

}