알고리즘매일매일

문제

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

지도의 한 변의 길이 N은 3 이상 8 이하의 정수이다. (3 ≤ N ≤ 8)
최대 공사 가능 깊이 K는 1 이상 5 이하의 정수이다. (1 ≤ K ≤ 5)
지도에서 가장 높은 봉우리는 최대 5개이다.
-> 이 조건들을 통해 완전 탐색을 해도 되겠다고 생각했다.

예전에 BFS로 길이를 배열에 저장해가며 풀었다가 메모리를 너무 많이 사용해서 DFS로 다시 풀었다.

DFS로 푸는 게 최대 depth를 저장하면 되므로 BFS보다 더 효율적인 듯하다.

BFS로도 잘 처리해주면 될 것 같지만 문제 맥락상(?) DFS가 더 맞는 것 같다.

문제를 잘 생각하고 알고리즘 사용하자!!

풀이

1. 값을 처음에 입력받으면서 가장 큰 값을 top 변수에 저장한다.
2. 배열을 탐색하며 top값과 같은 곳의 좌표를 ArrayList에 저장한다.
3. 모든 위치에 대해서 0번에서 K번 깎는 경우까지 모든 길이를 구해서 최댓값을 max에 저장한다.
4. max 출력.

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

public class Solution {
	static class Pair {
		int x;
		int y;
		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
    
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int N, K, max;
	static int[][] map;
	static boolean[][] check;
	static ArrayList<Pair> topList;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			topList = new ArrayList();
			
			int top = 0; //가장 높은 봉우리의 값을 저장
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if(top < map[i][j]) top = map[i][j];
				}
			}
			
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					if(map[i][j] == top) topList.add(new Pair(i,j));
				}
			}
            
			max = 0;
			construct();
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void construct() {
		for(int k=0; k<=K; k++) {
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					map[i][j] -= k;
					for(int l=0; l<topList.size(); l++) { //가장 높은 봉우리들에서부터 경로 탐색
						int x = topList.get(l).x;
						int y = topList.get(l).y;
						if(x == i && y == j) continue; //현재 탐색할 가장 높은 봉우리를 공사한 경우
						check = new boolean[N][N];
						check[x][y] = true;
						int tmp = dfs(x,y,1);
						if(tmp > max) max = tmp;
						
					}
					map[i][j] += k;
				}
			}
		}
	}
	
	static int dfs(int x, int y, int depth) {
		int d = depth;
        
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if(check[nx][ny]) continue;
			if(map[nx][ny] >= map[x][y]) continue;
            
			check[nx][ny] = true;
			d = Math.max(d,dfs(nx,ny,depth+1));
			check[nx][ny] = false;
			
		}

		return d;
	}

}

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo

문제

각 변에 다음과 같이 16진수 숫자(0~F)가 적혀 있는 보물상자가 있다.

보물 상자의 뚜껑은 시계방향으로 돌릴 수 있고, 한 번 돌릴 때마다 숫자가 시계방향으로 한 칸씩 회전한다.

각 변에는 동일한 개수의 숫자가 있고, 시계방향 순으로 높은 자리 숫자에 해당하며 하나의 수를 나타낸다.

보물상자에는 자물쇠가 걸려있는데, 이 자물쇠의 비밀번호는 보물 상자에 적힌 숫자로 만들 수 있는 모든 수 중, K번째로 큰 수를 10진 수로 만든 수이다.

N개의 숫자가 입력으로 주어졌을 때, 보물상자의 비밀 번호를 출력하는 프로그램을 만들어보자.

(서로 다른 회전 횟수에서 동일한 수가 중복으로 생성될 수 있다. 크기 순서를 셀 때 같은 수를 중복으로 세지 않도록 주의한다.)

 풀이

1. 상자의 변은 4개 이므로 N/4 만큼 회전을 하면 처음과 같은 상태가 되므로 N/4번 동안 각 변을 16진수 정수로 만들어주고(findPWD) 회전해주는(Rotate) 과정을 반복한다.
   1. 문자열을 N/4 크기만큼 잘라서 16진수 정수로 변환하여 box배열에 저장한다.
   2. box 배열에 들어있는 값이 현재 list에 존재하지 않는다면 list에 추가(중복 제거)
   3. 문자열의 마지막 문자를 맨 앞에 붙여줘서 회전을 해준다.
2. 모든 가능한 16진수를 만들어줬으면 정렬해준 후 K번째 큰 수를 구한다.
   1. K번째 큰 수를 10진수로 변환하기 위해 먼저 String으로 변환한다.
   2. String을 다시 10진수로 변환해서 출력.

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

public class Solution {
	static int N;
	static String s;
	static ArrayList&ltInteger> list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			s = br.readLine();
			list = new ArrayList&ltInteger>();

			for(int i=0; i<N/4; i++) {
				findPWD();
				rotate();
			}
			
			Collections.sort(list);
			String tmp = Integer.toString(list.get(list.size()-K));
			int ans = Integer.parseInt(tmp, 10);
			System.out.println("#"+tc+" "+ans);
		}
	}
	
	static void findPWD() {
		int[] box = new int[4];
		int k = N/4;
		
		int index = 0;
		for(int i=0; i<N; i+=k) {
			String tmp = s.substring(i, i+k);
			box[index++] = Integer.parseInt(tmp,16);
		}
		
		for(int i=0; i<4; i++) {
			if(!list.contains(box[i])) {
				list.add(box[i]);
			}
		}
	}
	
	static void rotate() {
		String last = s.substring(N-1);
		s = last+s.substring(0, N-1);
	}
}