모의 SW 역량테스트 (등산로 조정, 디저트 카페)

[등산로 조정 - 1949]

 

* 알고리즘

• 브루트 포스

 

* 로직

• 최대 높이 지점을 담아둔다
• 담아둔 각 좌표들을 하나씩 꺼내어 해당 좌표에서 갈 수 있는 가장 긴 등산로 길이를 구한다
  • 현재 위치를 기반으로 다음 움직일 좌표가 존재하면
    • 현재 위치의 높이 > 움직일 좌표의 높이 => 이동 가능
    • 현재 위치의 높이 < 움직일 좌표의 높이 => 1<= <=k까지 높이를 깎았을 때의 경우를 구한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Mountain_1949 {
	public int y, x;
	public int step;

	public Mountain_1949(int y, int x, int step) {
		super();
		this.y = y;
		this.x = x;
		this.step = step;
	}
}

public class Solution {

	static int N;
	static int K;
	static int[][] map;

	static int[][] dir = { { -1, 0, 1, 0 }, { 0, 1, 0, -1 } };
	static boolean[][] checked;

	static ArrayList<Mountain_1949> topPosition;
	static int answer;

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

		int testCase = Integer.parseInt(br.readLine());
		int t = 1;
		while (t <= testCase) {
			String config = br.readLine();
			st = new StringTokenizer(config, " ");
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];

			// map 받기
			topPosition = new ArrayList<>();
			int max = 0;
			for (int i = 0; i < N; ++i) {
				String input = br.readLine();
				st = new StringTokenizer(input, " ");
				for (int j = 0; j < N; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] > max) {
						topPosition = new ArrayList<>();
						topPosition.add(new Mountain_1949(i, j, 1));
						max = map[i][j];
					} else if (map[i][j] == max)
						topPosition.add(new Mountain_1949(i, j, 1));
				}
			}

			checked = new boolean[N][N];
			answer = 0;
			for (Mountain_1949 pos : topPosition) {
				int k = K;

				checked[pos.y][pos.x] = true;
				doSolution(pos, k);
				checked[pos.y][pos.x] = false;
			}

			System.out.println("#" + t + " " + answer);
			t++;
		}

	}

	private static void doSolution(Mountain_1949 pos, int k) {
		for (int i = 0; i < 4; ++i) {
			int moveY = pos.y + dir[0][i];
			int moveX = pos.x + dir[1][i];

			if (isRanged(moveY, moveX) && !checked[moveY][moveX]) {

				// 현재 위치의 높이 > 움직일 위치의 높이 -> 이동가능
				if (map[pos.y][pos.x] > map[moveY][moveX]) {
					checked[moveY][moveX] = true;
					doSolution(new Mountain_1949(moveY, moveX, pos.step + 1), k);
					checked[moveY][moveX] = false;
				}

				// 현재 위치의 높이 < 움직일 위치의 높이 -> k 사용해서 가는 경우 고려
				else {

					// k 사용해서 가는 경우 (단, k를 사용해서 갈 수 있는지 먼저 판별)
					for (int dig = 1; dig <= k; ++dig) {
						if ((map[moveY][moveX] - dig) < map[pos.y][pos.x]) {
							checked[moveY][moveX] = true;
							map[moveY][moveX] -= dig;

							doSolution(new Mountain_1949(moveY, moveX, pos.step + 1), 0);

							map[moveY][moveX] += dig;
							checked[moveY][moveX] = false;
						}					
					}
				}
			}
		}
		answer = Math.max(answer, pos.step);
	}

	private static boolean isRanged(int y, int x) {
		if (y >= 0 && y < N && x >= 0 && x < N)
			return true;
		return false;
	}
}

 

 

[디저트 카페 - 2105]

 

* 알고리즘

• 브루트포스

 

* 로직

• (0,0)부터 차례대로 한칸씩 기준좌표를 옮겨가며 모든 경우의 수를 고려한다
• 대각선으로 이동 할 때 2가지 경우를 고려한다
  • 원래 방향을 유지하는 경우 
  • 방향을 변경하는 경우
• 디저트의 수가 겹치면 안되기 때문에 disserts[]를 통해 조건처리한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	
	static int N;
	static int[][] map;
	static boolean[] disserts;
	static int[][] directions = {
			//오아, 왼아, 왼위, 오위
			{1, 1, -1, -1},
			{1, -1, -1, 1}
	};
	
	static int[] startPosition;
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int testCase = Integer.parseInt(br.readLine());
		int t=1;
		while(t<=testCase) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			int max = 0;
			for(int i=0; i<N; ++i) {
				String input = br.readLine();
				st = new StringTokenizer(input, " ");
				for(int j=0; j<N; ++j) {
					map[i][j] = Integer.parseInt(st.nextToken());
					max = Math.max(max, map[i][j]);
				}
			}
						
			answer = 0;
			startPosition = new int[2];
			disserts = new boolean[max+1];
			for(int i=0; i<N; ++i) {
				for(int j=0; j<N; ++j) {
					int count=1;
					int dir = 0;					
										
					startPosition[0] = i;
					startPosition[1] = j;					
					
					disserts[map[i][j]] = true;
					doSolution(i, j, count, dir);
					disserts[map[i][j]] = false;					
				}
			}
			
			answer = answer == 0 ? -1 : answer;
			System.out.println("#" + t + " " + answer);
			t++;
		}
		
	}

	private static void doSolution(int y, int x, int count, int dir) {
		if(dir == 4) return;
		if(dir == 3) {
			if(startPosition[0]+1 == y && startPosition[1]-1 == x) {
				answer = Math.max(answer, count);
				return;
			}						
		}		
				
		int moveY = y + directions[0][dir];
		int moveX = x + directions[1][dir];
		
		if(isRanged(moveY, moveX) && !disserts[map[moveY][moveX]]) {
			disserts[map[moveY][moveX]] = true;
			doSolution(moveY, moveX, count+1, dir);
			doSolution(moveY, moveX, count+1, dir+1);
			disserts[map[moveY][moveX]] = false;
		}		
	}

	private static boolean isRanged(int y, int x) {
		if(y>=0 && y<N && x>=0 && x<N) return true;
		return false;
	}
}