등산로 조성

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq

 

 

 

 

 

package swexpertmoitest;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * 1] t입력

	for(i 1~=t)
	
	  2] n(지도크기) / k(자를 수 있는 범위) 입력
	  3] a[n,n] 입력, 원본도 백업
	  4] 가장 높은 위치 찾기
	
	  5] 가장 높은 점 리스트 기준으로 반복문 수행
	      6] 지도에 대해서 for(;;)
							for(;;) 수행
	
	
	      7] 높은 위치 기점으로 한좌표 (1~k)만큼 깍기
	      8] 시작점에서 상하좌우 이동 -> dfs...
	      9] 점수계산(맥스와 비교해서 갱신)
	      10] 지도복구/ (7번)에서 
 * @author yky1990
 */
public class 등산로 
{	
	public static int t,n,k;
	public static int[][] map;
	public static boolean[][] v;
	public static ArrayList<Point> hPointsList = new ArrayList();
	public static ArrayList<Integer> ans = new ArrayList();
	public static int[] dx = new int[] {0,1,0,-1};
	public static int[] dy = new int[] {1,0,-1,0};
	public static int maxPt=0;
	public static int maxCnt=0;
	public static void main(String[] args) 
	{
		Scanner scan = new Scanner(System.in);
		t = scan.nextInt();
		
		for(int i=1;i<=t;i++) 
		{
			n = scan.nextInt();
			k = scan.nextInt();
			map = new int[n][n];
			inputMap(scan);
			findTallestPoints();
			hiking(i);
		}
		
		scan.close();
	}
	private static void hiking(int idx) {
		
		for(int i=0;i<hPointsList.size();i++) 
		{
			int curX = hPointsList.get(i).x;
			int curY = hPointsList.get(i).y;
			
			for(int a=0;a<n;a++) 
			{
				for(int b=0;b<n;b++) 
				{
					if(a==curX && b==curY) {continue;}//현재 기준점은 skip
					
					for(int x=1;x<=k;x++) // 지도 고치는 것
					{
						map[a][b] = map[a][b]-x;
						if(map[a][b]<0) {map[a][b] = map[a][b]+x;break;}
						int cnt=1;
						dfs(curX,curY,cnt);
						if(!ans.contains(maxCnt))ans.add(maxCnt);
						//복구
						map[a][b] = map[a][b]+x;
					}
				}
			}
		}
		System.out.println("#"+idx+" "+ans.get(ans.size()-1));
		maxPt=0;
		maxCnt=0;
		ans.clear();			
		hPointsList.clear();
	}
	private static void dfs(int curX, int curY,int cnt) {
		if(cnt>maxCnt)maxCnt=cnt;
		for(int i=0;i<4;i++) 
		{
			int nx = curX+dx[i];
			int ny = curY+dy[i];
			
			if(nx>=0 && ny>=0 && n>nx && n>ny) 
			{
				if( map[nx][ny]<map[curX][curY]) 
				{
					dfs(nx,ny,cnt+1);	
				}
			}
		}
	}
	private static void printMap() 
	{
		for(int i=0;i<n;i++) 
		{
			for(int j=0;j<n;j++) 
			{
				System.out.print(map[i][j]+" ");
			}System.out.println();
		}
	}
	private static void findTallestPoints() 
	{
		for(int i=0;i<n;i++){for(int j=0;j<n;j++) {if(map[i][j]==maxPt){hPointsList.add(new Point(i,j));}}}
	}
	
	private static void inputMap(Scanner scan) {
		for(int i=0;i<n;i++) 
		{
			for(int j=0;j<n;j++) 
			{
				map[i][j]=scan.nextInt();
				if(maxPt<map[i][j])maxPt=map[i][j];
			}
		}
	}
}
class Point
{
	int x;
	int y;
	public Point(int x,int y) 
	{
		this.x = x;
		this.y = y;
	}
	@Override
	public String toString() 
	{
		return "[x : "+x+" y : "+y+"]";
	}
}

 

 

 

 

2회차 (설계 & 구현 40분 소요)

package academymoi;

import java.util.ArrayList;
import java.util.Scanner;

public class 등산로조성 {
	public static int[] dx = { 0, 1, 0, -1 };
	public static int[] dy = { 1, 0, -1, 0 };
	public static int T, N, K;
	public static int[][] map;
	public static ArrayList<Point> hPointList = new ArrayList();
	public static int maxCnt = 0;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		T = scan.nextInt();
		for (int i = 1; i <= T; i++) {
			// 입력 & 가장 높은 부분 찾기
			input(scan);

			//
			mountainPath();
			System.out.println("#" + i + " " + maxCnt);
			maxCnt = 0;
			hPointList.clear();
		}

		scan.close();
	}

	private static void mountainPath() {

//		System.out.println(hPointList.toString());

		for (int i = 0; i < hPointList.size(); i++) {
			int stdx = hPointList.get(i).x;
			int stdy = hPointList.get(i).y;

			for (int a = 0; a < N; a++) {
				for (int b = 0; b < N; b++) {
					if (stdx == a && stdy == b)
						continue;
					else {
						// [1] 깍고 탐색하고 원복하고
						for (int x = 1; x <= K; x++) {
							map[a][b] = map[a][b] - x;

							// stdx,stdy 에서 탐색하고
							dfs(stdx, stdy, 1);

							// 원복하고
							map[a][b] = map[a][b] + x;

						}
					}
				}
			}

		}
	}

	private static void dfs(int stdx, int stdy, int cnt) {

		if (cnt >= maxCnt)
			maxCnt = cnt;
		// TODO Auto-generated method stub
		int nx = stdx;
		int ny = stdy;
		int val = map[nx][ny];

		for (int i = 0; i < 4; i++) {
			nx = stdx + dx[i];
			ny = stdy + dy[i];
//			System.out.println("nx:"+nx+" ny:"+ny);
			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				if (map[nx][ny] < val) {
					dfs(nx, ny, cnt + 1);
				}
			}
		}
	}

	/**
	 * 입
	 * @param scan
	 */
	private static void input(Scanner scan) {
		N = scan.nextInt();
		K = scan.nextInt();
		map = new int[N][N];
		int tm = 0;
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				map[j][k] = scan.nextInt();
				if (tm < map[j][k])
					tm = map[j][k];
			}
		}

		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				if (map[j][k] == tm) {
					hPointList.add(new Point(j, k));
				}
			}
		}
	}
}

class Point {
	int x;
	int y;

	public Point(int x, int y) {
		this.x = x;
		this.y = y;
	}

	@Override
	public String toString() {
		return "Point [x=" + x + ", y=" + y + "]";
	}

}