[CodeTree] 메이즈 러너 - Java

✨ 구현 👉 조건을 만족하는 가장 작은 크기의 정사각형을 찾고 시계방향으로 90도 회전 

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

---

📍 고려해야할 점

• 참가자가 현재 있는 칸 ~ 출구까지의 거리 < 참가자가 이동할 칸 ~ 출구까지의 거리 ➔ 이동 X
  • 출구까지의 최단거리가 더 가까워야 이동 가능
• 움직일 수 있는 칸이 2개 이상이라면 상하로 움직이는 것을 우선시
• 한 칸에 2명 이상의 참가자 있어도 가능 👉 List<Integer>[][] peopleLoc; 
• 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 찾기
  • 그러한 정사각형이 2개 이상이라면 행이 작은 것이 우선, 그래도 같으면 열이 작은 것이 우선
  • 선택된 정사각형은 시계방향으로 90도 회전하며 회전된 벽은 내구도-1

 

 

 

🕹️ 풀이방법

조건에 적합한 것이 여러 개 있을 때 우선되는 것들을 선택해야하고, 

가장 작은 정사각형을 찾는 것과 정사각형을 90도 회전하는 코드를 유의해서 작성해야 한다. 👉 이 부분에서 시간이 꽤 걸렸다. 

 

🔸 가장 작은 정사각형 찾기 

가장 작은 정사각형을 찾는 것은 단순하다. 

참가자 1명 이상과 출구를 포함하는 정사각형이므로 한 변의 길이는 최소 2이어야 한다. 

정사각형의 한 변의 길이가 sn이라고 할 때, (0, 0)칸 부터 (N-sn, N-sn)칸까지 정사각형을 일일이 만들면서

해당하는 정사각형 안에 참가자와 출구가 포함되는지를 확인하면 된다. 

 

가장 작은 크기를 가져야하고, 크기가 동일하다면 행이 작은 것, 그래도 같으면 열이 작은 것을 선택해야하기 때문에 우선 한 변의 길이가 2일 때부터 순차적으로 탐색한다.

정사각형이 시작하는 칸을 탐색하면서 참가자와 출구를 포함한다는 조건에 부합하는 정사각형이 나오면 바로 전체 반복문을  빠져나오도록 작성해야 회전시킬 수 있는 정사각형을 구할 수 있다. 

---

🔸 정사각형 회전 시키기 

정사각형 크기의 임의의 배열을 생성해서 회전된 결과값을 넣고 다시 maze배열에 반영시키는 방법으로 구현했다. 

참가자는 한 칸에 여러 명 있을 수 있으므로 참가자들의 위치정보와 탈출여부를 포함한 Info[] people과

참가자들의 위치를 참가자의 번호로 저장한 List<Integer>[][] peopleLoc 자료구조를 활용했다.

 

정사각형 범위에 참가자 번호가 포함되면 그 참가자의 위치를 회전시키고 나중에 putPeople() 메서드를 통해 peopleLoc에 반영시켜줄 것이다. 

---

🔹 move() : 참가자 이동시키기 

// 참가자 한 칸씩 이동 --> 출구까지 가까워져야 함 --> 움직일 수 있는 칸이 여러 개라면 상하 우선시
static void move() {

    for(int i=1; i<=M; i++) {
        Info p = people[i];
        int npx=0, npy=0;

        // 현재 위치에서 출구까지의 거리 
        int minDist = Math.abs(p.x-exitX)+ Math.abs(p.y-exitY);
        
        // 만약 참가자가 이미 탈출했으면 메서드 동작할 필요 X
        if(!p.escaped) {
            for(int d=0; d<4; d++) {
                int nx = p.x+dx[d];
                int ny = p.y+dy[d];

                // 범위를 벗어나거나 벽이 있으면 이동 불가
                if(inRange(nx, ny) && (maze[nx][ny]==0||maze[nx][ny]==-1)) {

                    // 현재 위치보다 이동한 위치가 출구에 더 가까운지 확인 
                    int nDist = Math.abs(nx-exitX)+ Math.abs(ny-exitY);
                    if(nDist<minDist) {
                        minDist = nDist;
                        npx = nx;
                        npy = ny;
                    }
                }
            }
        }

        // 현재 위치보다 더 가깝게 이동할 수 없다면 이동 X
        if(minDist == Math.abs(p.x-exitX)+ Math.abs(p.y-exitY))continue;
        
        // 이동 가능하다면 이동횟수 1 증가
        moveDist++;
        
        // 참가자 위치 변화
        p.x = npx;
        p.y = npy;

        // 출구에 도착했다면 탈출
        if(p.x==exitX && p.y==exitY) p.escaped=true;
    }
}

 

🔹 findSquare() : 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 찾기 

// 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 찾기 
// 가장 작은 크기를 갖는 정사각형이 여러 개라면 좌상단 x 좌표가 작은 것이 우선, 그래도 같으면 y 좌표가 작은 것이 우선
static void findSquare() {
    boolean isPeople = false; // 참가자 포함 여부 
    boolean isExit = false; // 출구 포함여부

	// 정사각형을 찾았다면 break loop을 통해 전체 반복문 빠져나오기 
    loop:
    // 한 변의 길이 (최소 길이=2)
    for(int n=2; n<=N; n++) {
    
    	// 정사각형의 시작점 (i, j) 찾기
        for(int i=0; i<=N-n; i++) {
            for(int j=0; j<=N-n; j++) {
                isPeople = false;
                isExit = false;
                
                // 정사각형 시작점으로부터 한 변의 길이까지 범위 탐색
                for(int ni=i; ni<i+n; ni++) {
                    for(int nj = j; nj<j+n; nj++) {
                        if(ni==exitX && nj==exitY) isExit=true;
                        if(peopleLoc[ni][nj].size()>0) isPeople=true;
                    }
                }

				// 한 명 이상의 참가자와 출구를 포함하는 정사각형을 찾았다면 break loop
                if(isExit && isPeople) {
                    sx = i;
                    sy = j;
                    sn = n;
                    break loop;
                }
            }
        }
    }
}

 

 

🔹 rotate() : 선택된 정사각형을 시계방향으로 90도 회전시키기 

// 미로 회전 --> 선택된 정사각형 시계방향으로 90도 회전 & 회전된 벽의 내구도 -1 
static void rotate() {

    int[][] sub = new int[sn][sn];
    int[][] sub2 = new int[sn][sn];

	// 선택된 정사각형 범위에 해당하는 정보를 sub 배열에 반영 
    for(int i=0; i<sn; i++) {
        for(int j=0; j<sn; j++) {
            sub[i][j] = maze[sx+i][sy+j];
        }
    }

	// sub 배열을 회전시키고 회전 결과를 sub2 배열에 반영 
    for(int i=0; i<sn; i++) {
        for(int j=0; j<sn; j++) {
            sub2[i][j] = sub[sn-j-1][i];
            
            // 정사각형에 포함되는 내구성-1 & 출구 정보 업데이트
            if(sub2[i][j]>0) sub2[i][j]--;
            if(sub2[i][j]<0) {
                exitX=i+sx;
                exitY=j+sy;
            }
        }
    }

    // 미로에 반영
    for(int i=0; i<sn; i++) {
        for(int j=0; j<sn; j++) {
            maze[i+sx][j+sy] = sub2[i][j];
        }
    }

    // 참가자 시계방향으로 90도 회전
    for(int i=0; i<sn; i++) {
        for(int j=0; j<sn; j++) {
            if(peopleLoc[i+sx][j+sy].size()>0) {
                for(int n=0; n<peopleLoc[i+sx][j+sy].size(); n++) {
                    int pIdx = peopleLoc[i+sx][j+sy].get(n);
                    Info now = people[pIdx];

                    now.x = j+sx;
                    now.y = (sn-i-1)+sy;
                }
            }
        }
    }
}

 

 

 

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class final_2023_1_메이즈러너 {
	static int N, M, K;
	static int[][] maze;
	static Info[] people;
	static int exitX, exitY;
	static int moveDist;
	static int sx, sy, sn; // 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 시작 좌표와 한변의 길이 
	static List<Integer>[][] peopleLoc;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Info{
		int x, y;
		boolean escaped;
		
		public Info(int x, int y, boolean escaped) {
			this.x=x;
			this.y=y;
			this.escaped=escaped;
		}
	}
	
	static void simulate() {
		while(K-->0) {

			move();
			if(checkEscape()) break;
			putPeople();
			findSquare();
			rotate();
			putPeople();
		}
	}
	
	// 참가자 한 칸씩 이동 --> 출구까지 가까워져야 함 --> 움직일 수 있는 칸이 여러 개라면 상하 우선시
	static void move() {
		
		for(int i=1; i<=M; i++) {
			Info p = people[i];
			int npx=0, npy=0;
			
			// 현재 위치에서 출구까지의 거리 
			int minDist = Math.abs(p.x-exitX)+ Math.abs(p.y-exitY);
			if(!p.escaped) {
				for(int d=0; d<4; d++) {
					int nx = p.x+dx[d];
					int ny = p.y+dy[d];
					
					// 범위를 벗어나거나 벽이 있으면 이동 불가 
					if(inRange(nx, ny) && (maze[nx][ny]==0||maze[nx][ny]==-1)) {
						
						// 현재 위치보다 이동한 위치가 출구에 더 가까운지 확인 
						int nDist = Math.abs(nx-exitX)+ Math.abs(ny-exitY);
						if(nDist<minDist) {
							minDist = nDist;
							npx = nx;
							npy = ny;
						}
					}
				}
			}
			
			// 현재 위치보다 더 가깝게 이동할 수 없다면 이동 X
			if(minDist == Math.abs(p.x-exitX)+ Math.abs(p.y-exitY))continue;
			moveDist++;
			p.x = npx;
			p.y = npy;
			
			// 출구에 도착했다면 탈출
			if(p.x==exitX && p.y==exitY) p.escaped=true;
		}
	}
	
	// 한 명 이상의 참가자와 출구를 포함한 가장 작은 정사각형 찾기 
	// 가장 작은 크기를 갖는 정사각형이 여러 개라면 좌상단 x 좌표가 작은 것이 우선, 그래도 같으면 y 좌표가 작은 것이 우선
	static void findSquare() {
		boolean isPeople = false; // 참가자 포함 여부 
		boolean isExit = false; // 출구 포함여부
		
		loop:
		// 한 변의 길이 (최소 길이=2)
		for(int n=2; n<=N; n++) {
			for(int i=0; i<=N-n; i++) {
				for(int j=0; j<=N-n; j++) {
					isPeople = false;
					isExit = false;
					for(int ni=i; ni<i+n; ni++) {
						for(int nj = j; nj<j+n; nj++) {
							if(ni==exitX && nj==exitY) isExit=true;
							if(peopleLoc[ni][nj].size()>0) isPeople=true;
						}
					}
					
					if(isExit && isPeople) {
						sx = i;
						sy = j;
						sn = n;
						break loop;
					}
				}
			}
		}
	}
	
	// 미로 회전 --> 선택된 정사각형 시계방향으로 90도 회전 & 회전된 벽의 내구도 -1 
	static void rotate() {
		
		int[][] sub = new int[sn][sn];
		int[][] sub2 = new int[sn][sn];
		
		for(int i=0; i<sn; i++) {
			for(int j=0; j<sn; j++) {
				sub[i][j] = maze[sx+i][sy+j];
			}
		}
		
		for(int i=0; i<sn; i++) {
			for(int j=0; j<sn; j++) {
				sub2[i][j] = sub[sn-j-1][i];
				if(sub2[i][j]>0) sub2[i][j]--;
				if(sub2[i][j]<0) {
					exitX=i+sx;
					exitY=j+sy;
				}
			}
		}
		
		// 미로에 반영
		for(int i=0; i<sn; i++) {
			for(int j=0; j<sn; j++) {
				maze[i+sx][j+sy] = sub2[i][j];
			}
		}
		
		// 참가자 시계방향으로 90도 회전
		for(int i=0; i<sn; i++) {
			for(int j=0; j<sn; j++) {
				if(peopleLoc[i+sx][j+sy].size()>0) {
					for(int n=0; n<peopleLoc[i+sx][j+sy].size(); n++) {
						int pIdx = peopleLoc[i+sx][j+sy].get(n);
						Info now = people[pIdx];
						
						now.x = j+sx;
						now.y = (sn-i-1)+sy;
					}
				}
			}
		}
	}
	
	// 모두 다 탈출했는지 확인
	static boolean checkEscape() {
		boolean flag = true;
		
		for(int i=1; i<=M; i++) {
			Info p = people[i];
			if(!p.escaped) {
				flag=false;
				break;
			}
		}
		return flag;
	}
	
	// 사람들의 위치를 미로에 반영시키기 
	static void putPeople() {
		peopleLoc = new ArrayList[N][N];
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				peopleLoc[i][j] = new ArrayList<>();
			}
		}
		
		for(int i=1; i<=M; i++) {
			Info p = people[i];
			if(!p.escaped) {
				peopleLoc[p.x][p.y].add(i);
			}
		}
	}
	
	
	static boolean inRange(int x, int y) {
		if(x>=0 && x<N && y>=0 && y<N) return true;
		else return false;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		maze = new int[N][N];
		people = new Info[M+1];
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				maze[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken())-1;
			int y = Integer.parseInt(st.nextToken())-1;
			people[i] = new Info(x, y, false);
		}
		
		st = new StringTokenizer(br.readLine());
		
		exitX = Integer.parseInt(st.nextToken())-1;
		exitY = Integer.parseInt(st.nextToken())-1;
		maze[exitX][exitY] = -1;
		
		simulate();
		bw.write(moveDist + "\n");
		bw.write((exitX+1) + " " + (exitY+1));
		bw.flush();
		bw.close();
	}
}

 

 

 

 

☀️ 효율적으로 90도 회전시키는 코드

다른 풀이법 중 내가 구현한 것보다 쉬운 코드가 있어서 기록한다.

sub배열을 사용하지 않고 (sx, sy)을 (0, 0)으로 옮겨서 구현한 코드이다. 

List<Integer>[][] peopleLoc을 굳이 만들지 말고 Info[] people만 이용해서 구현해도 충분하다.

 

// 정사각형 내부의 벽을 회전시킵니다.
public static void rotateSquare() {
    // 우선 정사각형 안에 있는 벽들을 1 감소시킵니다.
    for(int x = sx; x < sx + squareSize; x++)
        for(int y = sy; y < sy + squareSize; y++) {
            if(board[x][y] > 0) board[x][y]--;
        }

    // 정사각형을 시계방향으로 90' 회전합니다.
    for(int x = sx; x < sx + squareSize; x++)
        for(int y = sy; y < sy + squareSize; y++) {
            // Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            int ox = x - sx, oy = y - sy;
            // Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) -> (y, squareN - x - 1)가 됩니다.
            int rx = oy, ry = squareSize - ox - 1;
            // Step 3. 다시 (sx, sy)를 더해줍니다.
            nextBoard[rx + sx][ry + sy] = board[x][y];
        }

    // nextBoard 값을 현재 board에 옮겨줍니다.
    for(int x = sx; x < sx + squareSize; x++)
        for(int y = sy; y < sy + squareSize; y++) {
            board[x][y] = nextBoard[x][y];
        }
}

 

// 모든 참가자들 및 출구를 회전시킵니다.
public static void rotateTravelerAndExit() {
    // m명의 참가자들을 모두 확인합니다.
    for(int i = 1; i <= m; i++) {
        int x = traveler[i].x;
        int y = traveler[i].y;
        // 해당 참가자가 정사각형 안에 포함되어 있을 때에만 회전시킵니다.
        if(sx <= x && x < sx + squareSize && sy <= y && y < sy + squareSize) {
            // Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
            int ox = x - sx, oy = y - sy;
            // Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) -> (y, squareN - x - 1)가 됩니다.
            int rx = oy, ry = squareSize - ox - 1;
            // Step 3. 다시 (sx, sy)를 더해줍니다.
            traveler[i].x = rx + sx;
            traveler[i].y = ry + sy;
        }
    }

	// 출구에도 회전을 진행합니다.
    int x = exits.x;
    int y = exits.y;
    if(sx <= x && x < sx + squareSize && sy <= y && y < sy + squareSize) {
        // Step 1. (sx, sy)를 (0, 0)으로 옮겨주는 변환을 진행합니다. 
        int ox = x - sx, oy = y - sy;
        // Step 2. 변환된 상태에서는 회전 이후의 좌표가 (x, y) -> (y, squareN - x - 1)가 됩니다.
        int rx = oy, ry = squareSize - ox - 1;
        // Step 3. 다시 (sx, sy)를 더해줍니다.
        exits.x = rx + sx;
        exits.y = ry + sy;
    }
}