알고리즘매일매일

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

이 문제에서 어려웠던 부분은 웜홀 부분인 것 같다.

나는 웜홀의 좌표를 저장할 Wormhole클래스를 만들고 배열에 넣어주었다.

2차원 배열에 넣어서 각 6~10 번호마다 두 개씩 이므로 배열의 크기는 5X2가 된다. (웜홀은 쌍으로 존재하므로)

웜홀이 더 적게 존재할수도 있지만 최대 5개밖에 안되므로 그냥 한 번에 배열로 만들어줬다.

웜홀 배열의 각 좌표의 초기값을 -1로 설정해주고 이 점을 이용해서 두 개의 쌍을 차례대로 넣어준다.

예전에는 클래스를 만드는 대신에 3차원 int배열로 만들어 줬었다.(5X2X2 크기)

핀볼의 이동

1. 출발 위치와 진행 방향을 임의로 설정하여 점수의 최댓값을 구하는 문제이므로 모든 빈 칸(값이 0인 칸)에서 각 네 방향으로 출발해서 모든 경우의 점수를 구한다.
2. 각 이동에서는 블록의 모양에 따라서 적절히 방향을 잘 바꾸어 주며 이동시키고 블록이나 벽에 부딪힐 경우(범위 벗어나는 경우) 점수를 증가시킨다.
3. 웜홀을 만난 경우에는 방향을 유지한 채 반대편 웜홀로 이동한다.
4. 조건에 따라 핀볼이 출발 위치로 돌아오거나 블랙홀에 빠지는 경우가 될때까지 while문을 이용해 핀볼의 이동을 반복한다.
5. 핀볼의 이동이 끝나면 그때의 점수를 현재 최대 점수와 비교해준다.

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

public class Solution {
	
	static class Wormhole {
		int x;
		int y;
		Wormhole(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	static int N, max;
	static int[][] map;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static Wormhole[][] holeArr;
	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++) {
			N = Integer.parseInt(br.readLine());
			
			StringTokenizer st;
			map = new int[N][N];
			holeArr = new Wormhole[5][2];
			
            
            //웜홀의 위치 초기화 
			for(int i=0; i<5; i++) {
				for(int j=0; j<2; j++) {
					holeArr[i][j] = new Wormhole(-1,-1);
				}
			}
			
			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());
                    
                    //웜홀인 경우
                    //6번 웜홀부터 시작하므로 6번 웜홀이 0번째 index가 된다. 7번이 1, 8번이 2,,, 
					if(map[i][j] >= 6) {
                    
                    	//웜홀 첫 번째
						if(holeArr[map[i][j]-6][0].x == -1 && holeArr[map[i][j]-6][0].y == -1) {
							holeArr[map[i][j]-6][0].x = i;
							holeArr[map[i][j]-6][0].y = j;
						} else { //이미 첫 번째 웜홀의 위치가 저장되어 있는 경우 반대편 웜홀 저장
							holeArr[map[i][j]-6][1].x = i;
							holeArr[map[i][j]-6][1].y = j;
						}
					}
                    
				}
			}			
			
			max = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
                	
                    //빈칸이 아닌경우(블록이나 웜홀, 블랙홀인 경우)
					if(map[i][j] != 0) continue;
					
                    //상하좌우 각 방향으로 출발
					for(int k=0; k<4; k++) {
						move(i,j,k);
					}		
					
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void move(int x, int y, int dir) {
		
		int nx = x;
		int ny = y;
		int point = 0;
		
		while(true) {
        
        	//이동
			nx += dx[dir];
			ny += dy[dir];
			
            
            //벽에 부딪힌 경우 점수 증가하고 방향 전환
			if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
				point++;
				if(dir == 0 || dir == 2) {
					dir++;
				} else {
					dir--;
				}

				continue;
			}
			
            
            //블랙홀에 빠짐
			if(map[nx][ny] == -1) {
				break;
			}
			
            
            //출발위치로 돌아옴
			if(x == nx && y == ny) {
				break;
			}
			
            
            
			if(map[nx][ny] == 0) {
            	//빈칸이므로 방향유지한채 바로 이동
				continue;
			} else if(map[nx][ny] == 1) { //각 블록의 종류에따라서 방향을 변환해주고 점수도 증가
				if(dir == 0) {
					dir = 2;
				} else if(dir == 1) {
					dir = 0;
				} else if(dir == 2) {
					dir = 3;
				} else {
					dir = 1;
				}
				
				point++;
				
			} else if(map[nx][ny] == 2) {
				if(dir == 0) {
					dir = 1;
				} else if(dir == 1) {
					dir = 2;
				} else if(dir == 2) {
					dir = 3;
				} else {
					dir = 0;
				}
				
				point++;
				
			} else if(map[nx][ny] == 3) {
				if(dir == 0) {
					dir = 1;
				} else if(dir == 1) {
					dir = 3;
				} else if(dir == 2) {
					dir = 0;
				} else {
					dir = 2;
				}
				
				point++;
				
			} else if(map[nx][ny] == 4) {
				if(dir == 0) {
					dir = 3;
				} else if(dir == 1) {
					dir = 0;
				} else if(dir == 2) {
					dir = 1;
				} else {
					dir = 2;
				}
				
				point++;
				
			} else if(map[nx][ny] == 5) {
				if(dir == 0 || dir == 2) {
					dir++;
				} else {
					dir--;
				}
				
				point++;
				
			} else { //웜홀인 경우 반대편 웜홀로 이동
				int holenum = map[nx][ny]-6;
				if(nx == holeArr[holenum][0].x && ny == holeArr[holenum][0].y) {
					nx = holeArr[holenum][1].x;
					ny = holeArr[holenum][1].y;
				} else {
					nx = holeArr[holenum][0].x;
					ny = holeArr[holenum][0].y;
				}
			}
		}
		
        
        //이동이 끝난 후에 점수 비교
		if(max < point) {
			max = point;
		}
	}

}

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

처리해줘야 할 조건이 꽤 많은 문제였다.

1. 높이가 같아서 경사로를 안 놓아도 되는지
2. 높이가 다르다면 높이 차이가 2보다 적게 나서 경사로를 놓아줄 수 있는지
3. 경사로를 놓을 때 경사로가 범위를 벗어나지 않는지
4. 경사로를 놓는 곳의 높이는 같은지
5. 경사로가 이미 놓여져있지는 않은지

위의 조건들을 각 행과 열에 대해서 모두 검사해주어야 한다.

모든 행을 검사해주는 checkGaro와 모든 열을 검사해주는 checkSero 함수를 만들어서 테스트 케이스별로 각각 한 번씩 호출해서 답을 구하도록 했다. 각 행이나 열마다 위의 모든 조건을 만족하면 count를 해줬다.

더 자세한 설명은 코드의 주석 참고

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

public class Solution {

	static int N,X,count;
	static int[][] map;
    
	static boolean[][] garo;
	static boolean[][] sero;
    
	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());
			X = Integer.parseInt(st.nextToken());
			map = new int[N][N];
            
             //해당 위치에 경사로가 있는지 체크해줄 배열
			garo = new boolean[N][N];
			sero = new boolean[N][N];
			
			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());
				}
			}
			
			count = 0;
			
            //모든 행 검사
			checkGaro();
            
            //모든 열 검사
			checkSero();
			
			System.out.println("#"+tc+" "+count);
		}
	}
	
	static void checkGaro() {
		
		
		//모든 행을 검사 
		for(int i=0; i<N; i++) {
			boolean ok = true;
			
			//각 행에서 높이를 검사 
			for(int j=0; j<N-1; j++) {
				
                //높이가 같다면 다음 칸 비교로 넘어간다.
				if(map[i][j] == map[i][j+1]) {
					continue;
				}
				
                //앞의 칸이 뒤의 칸보다 더 큰 경우
				if(map[i][j] > map[i][j+1]) {
					if(map[i][j] - map[i][j+1] > 1) {
						//차이가 1보다 커서 경사로를 놓을 수 없다. 
						ok = false;
						break;
					}
					
					if(j+X >= N) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=j+1; k<=j+X; k++) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j+1] != map[i][k]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(garo[i][k]) {
							ok = false;
							break;
						}
					}
					
                    
                    //바로 위의 반복문에서 ok는 false값으로 break되어 나올 경우 break해준다.
					if(!ok) break;
					
                    
					//경사로를 놓는다.
					for(int k=j+1; k<=j+X; k++) {
						garo[i][k] = true;
					}
					
					
					//뒤의 칸이 앞의 칸보다 큰 경우
				} else if(map[i][j] < map[i][j+1]) {
					if(map[i][j+1] - map[i][j] > 1) {
						ok = false;
						break;
					}
					
					if(j+1-X < 0) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=j; k>=j+1-X; k--) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j] != map[i][k]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(garo[i][k]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=j; k>=j+1-X; k--) {
						garo[i][k] = true;
					}
				}
	
			}
			
            //해당 행이 모든 조건을 만족하여 ok가 true 값을 가지면 count값을 증가
			if(ok) count++;
		}
	}
	
	static void checkSero() {
		
		//모든 열을 검사 
		for(int j=0; j<N; j++) {
			boolean ok = true;
			
			//각 열에서 높이를 검사 
			for(int i=0; i<N-1; i++) {
				
                //높이가 같다면 다음 칸으로 넘어간다.
				if(map[i][j] == map[i+1][j]) {
					continue;
				}
				
                //앞의 칸이 뒤의 칸보다 더 큰 경우
				if(map[i][j] > map[i+1][j]) {
					if(map[i][j] - map[i+1][j] > 1) {
						//차이가 1보다 커서 경사로를 놓을 수 없다. 
						ok = false;
						break;
					}
					
					if(i+X >= N) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=i+1; k<=i+X; k++) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i+1][j] != map[k][j]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(sero[k][j]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=i+1; k<=i+X; k++) {
						sero[k][j] = true;
					}
					
					
				//뒤의 칸이 앞의 칸보다 더 큰 경우
				} else if(map[i][j] < map[i+1][j]) {
					if(map[i+1][j] - map[i][j] > 1) {
						ok = false;
						break;
					}
					
					if(i+1-X < 0) {
						//경사로를 놓으면 범위를 벗어난다.
						ok = false;
						break;
					}
					
					for(int k=i; k>=i+1-X; k--) {
						//경사로를 놓을 칸의 높이가 모두 같은지 검사 
						if(map[i][j] != map[k][j]) {
							ok = false;
							break;
						}
						
						//경사로가 이미 놓여져있는지 확인 
						if(sero[k][j]) {
							ok = false;
							break;
						}
					}
					
					if(!ok) break;
					
					//경사로를 놓는다.
					for(int k=i; k>=i+1-X; k--) {
						sero[k][j] = true;
					}
				}
						
			}
			
			if(ok) count++;
		}
	}

}

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

디저트 카페 문제는 아래 그림처럼 사각형 모양으로 움직여서 원점으로 돌아와야 한다.

원안의 숫자(디저트의 종류)가 겹치면 안 되며 범위를 벗어나도 안된다

더 자세한 조건은 문제 사이트 참고!
 

풀이

먼저 N의 범위가 크지 않으므로 모든 경우를 해볼 수 있다. 따라서 DFS를 이용해서 풀었다.

1. 각 칸을 시작점으로 하는 사각형을 모두 만들어준다. 
2. 사각형을 만들 수 없는 N-1 행과 N-2행, 0열과 N-1열은 시작점에서 제외한다.

move 함수로 DFS를 해주는데 조건을 잘 처리해주어야 한다.

1. 방향은 오른쪽 아래 방향(1,1), 왼쪽 아래 방향(1,-1), 왼쪽 위 방향(-1,-1), 오른쪽 위 방향(-1,1)의 순서를 정해놓고 움직인다.
2. 이동시킨 곳이 범위를 벗어나지 않아야 하고 방향은 3(시작점으로 돌아가는 마지막 방향)을 넘지 않는다.
3. 움직일 때마다 해당 디저트 종류를 ArrayList에 추가하였다. 계속 탐색을 진행하면서 디저트 종류가 ArrayList에 이미 포함되지 않은 경우에만 탐색을 계속 진행한다.(같은 디저트를 먹지 않는 조건)
4. 탐색을 할 때는 현재 방향을 유지해서 이동하는 경우와 방향을 꺾는 경우(dir 인덱스 증가)를 해주었다.
5. 탐색 시작점에서는 현재 방향을 유지하는 경우만 해줘야 한다(직사각형 모양을 위해 바로 꺾지 못함)
6. 현재 방향이 마지막 방향(오른쪽 위)이고 시작점에 돌아왔으면 max값과 디저트 종류를 추가한 ArrayList의 사이즈를 비교한 뒤 return 한다.

코드 주석에 설명 추가

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

public class Solution {
	
	static int N, max, sx, sy;
	static int[][] map;
	static int[] dx = {1,1,-1,-1};
	static int[] dy = {1,-1,-1,1};
	static ArrayList list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer st;
		for(int tc=1;tc<=T;tc++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			
			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());
				}
			}
            
            
			list = new ArrayList(); //디저트 종류를 추가할 list
			max = -1; //디저트를 먹을 수 없는 경우 -1을 출력하기 위해 -1로 할당
            
            
            //사각형을 만들 수 없는 곳을 제외한 모든 칸에서 탐색 시작
			for(int i=0; i<N-2; i++) {
				for(int j=1; j<N-1; j++) {
					sx = i;
					sy = j;
					list.add(map[sx][sy]);
					move(sx,sy,0);
					list.clear(); //다음 칸에서 출발하는 경우를 위해 list를 비워준다.
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
    
    //DFS
	static void move(int i, int j, int dir) {
		int x;
		int y;

		
        //현재 방향을 유지하며 이동하는 경우
		x = i+dx[dir];
		y = j+dy[dir];
		if(x >= 0 && y >= 0 && x < N && y < N) {
        
			if(dir == 3 && x == sx && y == sy) {
            	//사각형을 만들고 시작점으로 돌아온 경우
				if(max < list.size()) {
					max = list.size();
				}
				return;
			}
            
            //이동할 칸의 디저트가 list에 포함되어 있지 않아야한다.
			if(!list.contains(map[x][y])) {
				list.add(map[x][y]);
				move(x,y,dir);
				list.remove(list.size()-1);
			}
		}
		
		
        //방향을 꺾는 경우에는 dir+1을 해준 값으로 계산
		if(dir+1 == 4) return; //방향은 최대 3이므로
		if(dir == 0 &&i == sx && j == sy) return; //시작점에서는 꺾을 수 없다.
		x = i+dx[dir+1];
		y = j+dy[dir+1];
		
		if(x >= 0 && y >= 0 && x < N && y < N) {
        
			if(dir+1 == 3 && x == sx && y == sy) {
            	//사각형을 만들고 시작점으로 돌아온 경우
				if(max < list.size()) {
					max = list.size();
				}
				return;
			}
            
            //이동할 칸의 디저트가 list에 포함되어 있지 않아야한다.
			if(!list.contains(map[x][y])) {
				list.add(map[x][y]);
				move(x,y,dir+1);
				list.remove(list.size()-1);
			}
		}		
	}

}

더 빠른 시간안에 문제를 해결한 사람들의 코드를 보면 dfs를 사용하지 않고 반복문만을 사용하였다. 속도가 거의 두배 넘게 차이가 나는 것 같다. 물론 백트랙킹을 더 잘해주면 차이가 더 적게 날 수도 있을 것 같다... 다음에 dfs를 사용하지 않고 다시 풀어봐야겠다.