알고리즘매일매일

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=AV5V1SYKAaUDFAWu

Fail을 엄청 많이 한 문제였다ㅠㅠ 심지어 이번에 다시 풀어본 것임에도 불구하고 4번 만에 Pass 했다...

보호 필름 문제는 dfs를 사용하여 각 막에 약물 A를 투여하는 경우, B를 투여하는 경우, 약물을 투여하지 않는 경우를 모두 구해줬다.

이 문제에서주의할 점은 합격 기준인 K가 1인 경우다.

K가 1인 경우 무조건 합격이므로 검사를 해줄 필요 없이 바로 0을 출력해주어야 한다.

완전 탐색

먼저 K==1 인 경우에는 0을 출력해주도록 처리하고 바로 다음 테스트 케이스로 넘어간다.

K가 1보다 큰 경우에는 각 막에 약품을 투여하여 변경된 상태를 새로 적용해주기 위해서 매번 새로운 배열을 만들어주었다.(메모리를 많이 써서 다른 방법을 쓰는 게 좋을 것 같다...)

현재 투여한 약물의 수가 이미 기준을 통과한 최솟값을 넘어간다면 더 검사할 필요가 없으므로 return 하도록 백트래킹을 해준다.

매번 dfs에서는 합격하는지 검사해주고 기준을 통과했다면 min값을 바꾸고 return 한다.(통과한 시점에서 더 많은 약물을 투여할 필요가 없기 때문)

모든 막에 대한 약물 투여 여부를 결정해준 경우에도 return.

합격 기준 검사

합격 기준을 검사하는 부분에서는 모든 열에 대해서 합격 기준을 통과하는지 검사해준다.

하나의 열이라도 합격기준을 통과하지 못하면 합격하지 못한다.

각 열에 대해서는 연속하는 K개의 셀이 같은 값인지 검사해주고 한 번이라도 그러한 경우가 있다면 다음 열의 검사로 넘어간다.

import java.io.*;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int D,W,K, min;
    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());
            D = Integer.parseInt(st.nextToken());
            W = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
 
            int[][] film = new int[D][W];
            for(int i=0; i<D; i++) {
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<W; j++) {
                    film[i][j] = Integer.parseInt(st.nextToken());
                }
            }
 
 			
            //합격 기준이 1인 경우 바로 0을 출력하고 다음 테스트 케이스로 넘어간다.
            if(K == 1) {
                System.out.println("#"+tc+" "+0);
                continue;
            }
             
             
            min = D+1; //약물을 투여하는 최대 개수는 D개이므로 적당히 D+1정도로 설정해주었다.
            dfs(film,0,0);
            System.out.println("#"+tc+" "+min);
        }
    }
     
    static void dfs(int[][] film, int index, int count) {
    	//현재 약품 투여 횟수가 이미 최솟값을 넘은 경우 더 검사할 필요가 없으므로 return
        if(count >= min) return; 
        
        
        //합격 기준을 통과한 경우 최솟값을 count값(현재 약품 투여 횟수)으로 변경하고 return
        if(test(film)) {
            min = count;
            return;
        }
        
        
        //막의 범위를 넘어가는 경우 return
        if(index == D) return;
         
         
        //새로 넘겨줄 배열 생성
        int[][] arr = new int[D][W];
        for(int i=0; i<D; i++) {
            for(int j=0; j<W; j++) {
                arr[i][j] = film[i][j];
            }
        }
         
         
        //index행에 약품을 투여하지 않는 경우
        dfs(arr,index+1,count);
         
         
        //index행에 A약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 0;
        }
        dfs(arr,index+1, count+1);
        
        
        //index행에 B약품을 투여하는 경우
        for(int j=0; j<W; j++) {
            arr[index][j] = 1;
        }
        dfs(arr,index+1, count+1);
         
    }
     
    static boolean test(int[][] film) {
        boolean flag = false;
 
 		//모든 열을 검사 
        for(int j=0; j<W; j++) {
        
        	//각 열의 셀을 모두 검사 
            for(int i=0; i<=D-K; i++) {
                flag = true;
                
                //각 열에서 K개만큼의 연속적인 셀을 검사 
                for(int l=i+1; l<i+K; l++) {
                    if(film[i][j] != film[l][j]) {
                        flag = false; //K개만큼 연속적으로 같지 않으면 break 하고 밑의 셀부터 다시 검사 
                        break;
                    }
                }
                 
                //K개 연속적으로 같은 셀이 있으면 한 번이라도 있으면 이번 열은 바로 통과하고 다음 열로 넘어간다.
                if(flag) break;                 
            }
             
            //이번 검사한 열이 검사를 통과하지 못하므로 아예 테스트 통과 불가능 
            if(!flag) break;
        }
         
        if(!flag)
            return false;
        else
            return true;
    }
     
}

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를 사용하지 않고 다시 풀어봐야겠다.

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

풀이

1. 먼저 각 자석의 자성 정보를 배열에 저장한다.
2. 입력받은 K번만큼 실행
   1. 회전시킬 자석 번호와 방향을 입력받는다.
   2. 처음 상태에 따라서 회전할지 안 할지가 결정되므로 미리 회전방향을 배열에 저장해놓는다.
   3. 회전시킬 자석의 오른쪽과 왼쪽의 자석들을을 각각 순차적으로 검사한다.
   4. 앞의 자석의 2번째 날과 뒤의 자석의 6번째 날을 비교한다.
   5. 같으면 그쪽 방향의 자석들은 회전하지 않을 것이므로 break
   6. 다르면 현재 회전하는 자석의 반대 방향으로 회전 방향을 저장한다.
   7. 각 자석을 위에서 저장한 회전 정보를 이용하여 회전시켜준다.
      1. 0인 경우는 회전하지 않는 자석
      2. 1인 경우는 시계방향 회전
      3. -1인 경우는 반시계 방향 회전
3. K번만큼의 회전이 끝난 후에 총점을 계산해준다.
4. 1,2,4,8 순으로 점수가 늘어나므로 left shift (<<) 연산을 사용해서 sum 변수에 더해줬다.

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

public class Solution {

	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++) {
			int K = Integer.parseInt(br.readLine());
			int[][] info = new int[4][8];
			for(int i=0; i<4; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<8; j++) {
					info[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
            //명령을 K번 실행
			for(int i=0; i<K; i++) {
				st = new StringTokenizer(br.readLine());
				int num = Integer.parseInt(st.nextToken())-1;
				int dir = Integer.parseInt(st.nextToken());
                
				int[] rotation = new int[4]; //회전할 방향을 저장
				rotation[num] = dir;
				
                
                //오른쪽 자석들을 검사
				for(int j=num+1; j<4; j++) {
					if(info[j-1][2] == info[j][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j-1];
				}
				
                
                //왼쪽 자석들을 검사
				for(int j=num-1; j>=0; j--) {
					if(info[j][2] == info[j+1][6]) //자성이 같으면 회전하지 않는다.
						break;
					else
						rotation[j] = -rotation[j+1];
				}
				
				
                //각 자석을 회전시킨다.
				for(int j=0; j<4; j++) {
					if(rotation[j] == 0) continue; //회전하지 않는 경우
					else if(rotation[j] == 1) { // 시계방향 회전
						int tmp = info[j][7];
						for(int k=7; k>0; k--) {
							info[j][k] = info[j][k-1];
						}
						info[j][0] = tmp;
					} else if(rotation[j] == -1) { // 반시계방향 회전
						int tmp = info[j][0];
						for(int k=0; k<7; k++) {
							info[j][k] = info[j][k+1];
						}
						info[j][7] = tmp;
					}
				}
				
			}
			
            
            //모든 실행이 끝난 후 총합을 계산
			int sum = 0;
			for(int i=0; i<4; i++) {
				if(info[i][0] == 1) {
					sum += 1<<i;
				}
			}
			
			System.out.println("#"+tc+" "+sum);
		}	
	}

}

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

풀이

1. 먼저 사용자들의 이동 정보를 각 배열에 저장하고 BC의 정보는 AP클래스를 만들어서 ArrayList에 저장하였다.
2. 시간에 따라 이동하면서 각 시간마다 A와 B의 충전량 합의 최댓값을 구해준다.
   1. 최댓값은 사용자가 각각 사용할 수 있는 충전량을 배열에 저장해놓고 모든 경우를 구해줬다.
   2. 이때 i == j 인 상황이 됐을 때 한쪽은 0 (해당 BC를 사용할 수 없는 경우)일 수도 있으므로 무조건 반으로 나눠주면 안 되고 둘 다 해당 BC를 이용하고 있는지 확인해주어야 한다. (같은 p값을 가지는지 확인)
3. 시간마다의 최댓값을 모두 더해준 후에 출력

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

public class Solution {
	static class AP {
		int x;
		int y;
		int c;
		int p;
		AP(int x, int y, int c, int p) {
			this.x = x;
			this.y = y;
			this.c = c;
			this.p = p;
		}
	}
	
	static int M,A;
	static int dx[] = {0,-1,0,1,0};
	static int dy[] = {0,0,1,0,-1};
	static int Ainfo[];
	static int Binfo[];
	static ArrayList aplist;
    
	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());
			M = Integer.parseInt(st.nextToken());
			A = Integer.parseInt(st.nextToken());
			Ainfo = new int[M];
			Binfo = new int[M];
			
            //사용자 A의 이동정보
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<M; i++) {
				Ainfo[i] = Integer.parseInt(st.nextToken());
			}
			
            //사용자 B의 이동정보
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<M; i++) {
				Binfo[i] = Integer.parseInt(st.nextToken());
			}
			
            //BC의 정보를 ArrayList에 저장한다.
			aplist = new ArrayList();
			for(int i=0; i<A; i++) {
				st = new StringTokenizer(br.readLine());
				
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int p = Integer.parseInt(st.nextToken());
				
				aplist.add(new AP(x,y,c,p));
			}
			
			int ans = move();
			System.out.println("#"+tc+" "+ans);
		}
	}
	
    
	static int move() {
		int x1 = 1;
		int y1 = 1;
		int x2 = 10;
		int y2 = 10;
        
        //0초일때의 합
		int sum = getMax(x1,y1,x2,y2);
		
        //시간별로 이동하면서 그때마다의 최대값을 합해준다.
		for(int time=0; time<M; time++) {
			x1 += dx[Ainfo[time]];
			y1 += dy[Ainfo[time]];
			x2 += dx[Binfo[time]];
			y2 += dy[Binfo[time]];
			sum += getMax(x1,y1,x2,y2);
		}
		
		return sum;
	}
	
    
	static int getMax(int x1, int y1, int x2, int y2) {
		int[][] amount = new int[2][A];
		//2차원 배열에 사용자A(0)와 사용자B(1)의 BC별로 충전가능한 값을 저장해준다.
        
        //사용자A의 충전 가능한 BC의 p값
		for(int j=0; j<A; j++) {
				amount[0][j] = check(x1,y1,j);
		}
		
        //사용자B의 충전 가능한 BC의 p값
		for(int j=0; j<A; j++) {
			amount[1][j] = check(x2,y2,j);
			
		}
		
        //사용자 A와 사용자 B의 충전량의 합중 최댓값을 구해준다.
		int max = 0;
		for(int i=0; i<A; i++) {
			for(int j=0; j<A; j++) {
				int sum = amount[0][i]+amount[1][j];
                
                 // 같은 BC를 이용하는 경우 값을 반으로 나눠줘야한다.
                 // 주의할 점은 한 쪽은 아예 값이 0일수도 있으므로(해당 BC를 이용할 수 없는 위치) 정확히 둘다 같이 이용하고 있는 경우에만 나누어주어야한다.
				if(i == j && amount[0][i] == amount[1][j])
					sum /= 2;
				if(sum > max) max = sum;
			}
		}

		return max;
	}
	
	static int check(int x, int y, int apnum) {

		int a = Math.abs(x-aplist.get(apnum).x);
		int b = Math.abs(y-aplist.get(apnum).y);
		int dist = a+b;
        
        //해당 BC에 포함되는 경우에 p값을 리턴
		if(dist <= aplist.get(apnum).c)
			return aplist.get(apnum).p;
		else
			return 0;
	}
	
}

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

1. 1 ≤ N ≤ 4

2. 2 ≤ W ≤ 12

3. 2 ≤ H ≤ 15

범위가 위와 같기 때문에 완전 탐색을 해주면 된다. 연쇄적으로 깨질 벽돌은 큐를 사용하여 관리해줬다.

풀이

1. 벽돌을 깨는 경우를 모든 열에 대해서 구해준다.
2. 열을 선택하면 그 열에서 구슬에 처음 닿을 벽돌(행)을 찾아준다.
3. 이제 위에서 찾은 벽돌에서부터 해당 칸의 값-1만큼 연쇄적으로 깨 주고 빈 공간을 채워주어야 한다.
   1. 먼저 새로 배열을 만들어야 한다. (매번 깨지는 모양이 다르므로)
   2. 깨뜨릴 벽돌들(값이 2 이상)의 정보를 큐에 넣어주고 매번 큐에서 꺼내서 깨뜨린다. (값이 0인 경우는 그냥 넘어가고 1인 경우에는 해당 칸을 0으로 만든 후 넘어간다)
   3. 큐에 있는 벽돌들을 제거해줬으면 이제 빈 공간을 정리해준다.
4. 빈칸을 채울 때는 모든 열에서 마지막 행부터 순차적으로 검사한다.
   1. 0인 곳(비어있는 곳)을 찾아서 더 위칸에서 0이 아닌 값을 찾아 옮겨준다.
   2. 위쪽 칸들이 모두 0인 경우에는 다음 열로 넘어간다.
5. 다음 구슬을 쏘기 위해서 구슬을 쏜 횟수인 cnt값을 증가시킨 후 위의 과정을 반복한다.
6. cnt값이 N이 되었다면 남은 벽돌의 최소 개수를 구해준다.
7. 최솟값을 출력하거나 벽돌이 모두 깨져서 최솟값을 계산해주지 못하고 초기값인 경우에는 0을 출력한다.

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

public class Solution {

	static class Pair {
		int x;
		int y;
		int num;
		Pair(int x, int y, int num) {
			this.x = x;
			this.y = y;
			this.num = num;
		}
	}
	
	static int N,W,H,min;
	static Queue q;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	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());
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			int[][] map = new int[H][W];
			for(int i=0; i<H; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
            
			min = -1;
			solve(0,map);
            
			if(min == -1) //벽돌이 모두 깨진 경우
				System.out.println("#"+tc+" "+0);
			else
				System.out.println("#"+tc+" "+min);
		}
	}
	
    
	static void solve(int cnt, int[][] arr) {
		if(cnt == N) {
			int remain = 0;
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					if(arr[i][j] != 0)
						remain++;
				}
			}
            
			if(min == -1 || min > remain)
				min = remain;	
			return;
		}
		
        //모든 열에 대하여 구슬을 쏘는 경우를 구해준다.
		for(int j=0; j<W; j++) {
			int i = 0;
			while(i < H) {
				if(arr[i][j] != 0) break;
				i++;
			}
			
			if(i == H) continue; //해당 열이 모두 빈칸이라 다음 열로 넘어간다.
			
			int[][] arr2 = copyArr(arr);
			crush(i,j,arr2); //깨뜨리기
			move(arr2); // 빈 칸 정리
			solve(cnt+1,arr2); // 다음 구슬 쏘기
		}
	}
	
    
	static void move(int[][] arr) {
		for(int j=0; j<W; j++) {
			for(int i=H-1; i>0; i--) {	
				if(arr[i][j] == 0) {
                	//빈 칸을 찾으면 해당 빈칸 보다 위쪽 칸을 검사한다.
					int k = i-1;
					while(k >= 0) {
						if(arr[k][j] != 0) { //떠 있는 벽돌(빈 칸이 아닌 칸)을 발견하면
							arr[i][j] = arr[k][j]; //아래로 옮겨주고
							arr[k][j] = 0; //해당칸은 비워준다.
							break;
						}
						k--; //위쪽 칸을 계속 검사
					}
					if(k == -1) break; // 위쪽칸들이 모두 0인 경우 해당 열을 더 검사할 필요가 없으므로 다음 열로 넘어간다.
				}
			}
		}
	}
	
    
	static void crush(int x, int y, int[][] arr) {
		q = new LinkedList();
		q.add(new Pair(x,y,arr[x][y]));
		arr[x][y] = 0;
		
		while(!q.isEmpty()) {
			Pair p = q.remove();
			for(int i=0; i<4; i++) {
				int nx = p.x;
				int ny = p.y;
				int num = p.num;
				for(int j=0; j<num-1; j++) {
					nx += dx[i];
					ny += dy[i];
					if(nx < 0 || nx >= H || ny < 0 || ny >= W) break;
					if(arr[nx][ny] == 0) continue;					
					if(arr[nx][ny] > 1)
						q.add(new Pair(nx,ny,arr[nx][ny]));
					arr[nx][ny] = 0; //깨트리기	
				}
	
			}
		}
	}
	
    
	static int[][] copyArr(int[][] arr) {
		int[][] newArr = new int[H][W];
		for(int i=0; i<H; i++) {
			for(int j=0; j<W; j++) {
				newArr[i][j] = arr[i][j];
			}
		}
		return newArr;
	}

}

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

이번에는 두 가지 방법으로 풀어보았다. 사실 첫 번째 풀이(BFS)로 풀고 다른 사람들 실행 시간과 비교해봤을때 엄청 빠르게 푼 사람이 있어서 다른 사람들 풀이 좀 찾아보고 다시 풀어봤다ㅠㅠ 두 번째 풀이가 훨씬 빠를 뿐만아니라 메모리 차이도 엄청나다...

첫 번째 풀이 (BFS 풀이)

1. K 값이 커질 때마다 BFS가 단계별로 진행하는 모양과 같기 때문에 BFS로 풀었다.
2. N의 범위가 (5 ≤ N ≤ 20) 이므로 완전 탐색을 해줬다.
3. 모든 칸에 대해서 bfs를 통해 서비스 영역 모양 처럼 퍼지도록 계산해줬다.
4. K 값이 증가할때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
   1. K 값이 바뀌는 것은 큐 사이즈를 저장해놨다가 큐 사이즈 만큼을 진행해주고 나면된다.
   2. 예를 들어 K=1 일때 큐 size 는 1이고 K=2 일때 size는 4, K=4 일때 size = 8 이다.
   3. K 값이 바뀔 때마다 calc 함수에서 최대 서비스할 수 있는 집의 개수를 세서 리턴한다.

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 N,M,max;
	static int[] dx = {0,0,1,-1};
	static int[] dy = {1,-1,0,0};
	static int[][] city;
	static Queue q = new LinkedList();
	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());
			M = Integer.parseInt(st.nextToken());
			
			city = new int[N][N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					city[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			max = 0;
            
            //모든칸 탐색
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					bfs(i,j);
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void bfs(int i, int j) {
		
		boolean check[][] = new boolean[N][N];
		q.add(new Pair(i,j));
		check[i][j] = true;
		int homecnt = 0;
		int k = 1;
		int size = q.size(); //처음 큐 사이즈 저장( 1값을 저장)
		while(!q.isEmpty()) {
			
			//K 값이 증가할 때마다 서비스를 받는 집의 수를 계산하고 최댓값을 저장한다.
			homecnt = calc(k++, check);
			if(max < homecnt) {
				max = homecnt;
			}
			
			size = q.size(); //단계별로 진행하기 위해서 매번 들어가있는 큐사이즈를 구해준다
			while(size-- > 0) { //size 만큼 탐색 진행
				Pair p = q.remove();
				int x = p.x;
				int y = p.y;

				int cnt = 0;
				for(int l=0; l<4; l++) {
					int nx = x+dx[l];
					int ny = y+dy[l];
					if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
					if(check[nx][ny]) continue;
					q.add(new Pair(nx,ny));
					check[nx][ny] = true;
					if(city[nx][ny] == 1) cnt+= 1;
				}
			}
			
			
		}
	}
	
	static int calc(int k, boolean[][] check) {
		int homecnt = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(check[i][j] && city[i][j] == 1) {
					homecnt += 1; //방문 한 곳(서비스 영역)중에 집이 있으면 집의 수를 count
				}
			}
		}
		
		int cost = (k*k)+((k-1)*(k-1));
		int profit = homecnt*M - cost;
		if(profit >= 0) //마이너스 값이 아닌 이상 손해가 아니다
			return homecnt;
		else
			return 0;
	}

}

두 번째 풀이

1. 모든칸에 대해서 K값에 따른 최대 집의 개수를 구해준다.
2. 집의 K값의 모양을 구하는식은
   1. 현재 칸이 x, y 라고 했을 때 모든 칸 i, j 에 대해서 계산해준다.
   2. K = |i-x| + |j-y|  를 계산해서 다음과 같이 구할 수 있다.
3. K=2 일때 위의 식을 사용하면 다음과 같이 된다.

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

public class Solution {

	static int N,M,max;
	static int[][] city;
	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());
			M = Integer.parseInt(st.nextToken());
			
			city = new int[N][N];
			for(int i=0; i<N; i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<N; j++) {
					city[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			max = 0;
			for(int i=0; i<N; i++) {
				for(int j=0; j<N; j++) {
					calc(i,j);
				}
			}
			
			System.out.println("#"+tc+" "+max);
		}
	}
	
	static void calc(int x, int y) {
        for (int k = 0; k < N + 2; k++) {
        	//K가 최대 N*N 칸을 모두 채우는 범위까지 진행
            int homecnt = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int nx = Math.abs(i - x);
                    int ny = Math.abs(j - y);
                    if (nx + ny < k && city[i][j] == 1) {
                    	//현재 K 일때의 서비스 영역이고, 집이 있으면 집의 수를 count 해준다.
                        homecnt++;
                    }
                }
            }
            int profit = (homecnt * M) - (k * k + (k - 1) * (k - 1)); //수익 계산
            if (profit < 0)
                continue;
            else
                max = Math.max(homecnt, max); //손해를 보지 않으면 집의 수를 최댓값과 비교하여 더 크면 저장.
        }
    }
	

}