[삼성기출 코드트리][Java] 마법의숲 탐색 - 골드3

2024 상반기 오후 1번문제 (A형 st)

 

1. 문제 

https://www.codetree.ai/problems/magical-forest-exploration/description

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

와 ... 싸피때 A형 준비한 이후로 이렇게 머리아픈 문제 간만에 본다

진짜 "그대로"가 중요한데 그 그대로 구현하는게 빡세다

 

해설 보니까 100줄로 정리되던데 나는 디버깅위한 함수 포함해서 300줄 넘음 (최적화 안함, 코드 예쁘게 안짬)

해설 보시려는분은 뒤로가기 해주세요 .. 

 

 

2. 접근법

 

나는 문제를 읽고 일단 필요 method부터 생각하는 편이다

어떻게 구현할지는 눈으로 생각이 안나기때문ㅇ.. 

 

1) checkD - 밑으로 내려갈수있는지 확인

2) checkLR  - 왼쪽 또는 오른쪽으로 내려갈수있는지 확인

3) down - 내려가기, 출구 방향 안바뀜

4) rotateL, rotateR - 돌면서 내려가기, 출구방향 바뀜

5) check - 이건 무조건 bfs,dfs, 배열에 항상 나오는 범위 체크 메소드

6) resetMap - 범위 넘는애가 들어오면 다 리셋!!

7) moveSouth - bfs로 가장 남쪽 행을 리턴

그리고 그림처럼 구현하면서 디버깅해보는게 **정말 중요**

while문을 돌면서 checkD -> checkLR(L)->checkLR(R) 을 계속 확인하고

down,rotateL,rotateR 로 map을 채워준다 (골렘 이동)

 

골렘이 더이상 남쪽으로 내려갈 수없으면

r이 1~3 인 map에 0이 아닌 값이 들어있으면 reset 해버림 (골렘 다나가)

 

그러면서 현재 정령의 위치로 moveSouth BFS를 돌린다 .. 

-BFS로는 범위 나가거나 or 0인 값(아무것도없음) or 이미 방문한 곳은 continue;

-같은 골렘 끼리는 출구나 같은값으로 정령이 이동할수 있고//내가지금 출구라면 어디든 갈수있다

 

 

 

 

3. 코드

package boj;
import java.io.*;
import java.util.*;

public class CT마법의숲 {
	static int r,c;
	static int k; //정령의 
	static int start; // 시작 행 
	static int ci; //시작 열 
	static int end; //출구방
	static int[][] map;
	static int cnt;
	static int ans;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		map = new int[r+3][c];
		
		for(int i=0;i<k;i++) {
			
			cnt =0 ;
			st = new StringTokenizer(br.readLine());
			ci = Integer.parseInt(st.nextToken())-1;//시작 열 
			end = Integer.parseInt(st.nextToken());
			
			start = 1; //시작 행 
			
			//시작
			int dx[] = {-1,0,1,0,0};
			int dy[] = {0,1,0,-1,0};
			
			for(int l=0; l<5;l++) {
				int t1 = start + dx[l];
				int t2 = ci+dy[l];
					
				map[t1][t2] = 1;
			}
	
			
			while(true) {	
				
				if(checkD(start,ci)) {
					down(start,ci,i);
					start++;
					//printMap();
				}
				else if(checkLR('L',start,ci)) {
					//System.out.println("왼쪽이라두... ");
					rotateL(start,ci,i);
					start++;
					ci--;
				}
				else if(checkLR('R',start,ci)) {
					//System.out.println("오른 쪽이라두... ");
					rotateR(start,ci,i);
					start++;
					ci++;
				}
				else {
					break;
				}
			
			}
			
			//System.out.println( (i+1)+"번째 정령 ");
			//printMap();
			
			boolean isReset = false;
			for(int q=0;q<3;q++) {
				for(int w=0;w<c;w++) {
					if(map[q][w]!=0) {
						isReset=true;
					}
				}
			}
			//만약 다돌렸는데 삐져나오면 reset
			if(isReset) {
				resetMap();
			}
			else {
				//System.out.println("r : "+ (moveSouth(start, ci, i)-2));
				//System.out.println();
				ans = ans + (moveSouth(start, ci,i)-2);
			}
			
			//System.out.println( (i+1)+"번째 정령 ");
			//printMap();
			//System.out.println();
			
		}
		System.out.println(ans);
	}
	private static int moveSouth(int x, int y, int id) {
		int temp = 0;
		int[] dx= {1,-1,0,0};
		int[] dy= {0,0,-1,1};
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visit = new boolean[r+3][c];
		
		q.offer(new int[] {x,y});
		temp = x;
		visit[x][y] = true;
		
		//System.out.println(x+","+y);
		
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			int arrx = arr[0];
			int arry = arr[1];
			
			for(int i=0;i<4;i++ ) {
				int nx = arrx + dx[i];
				int ny = arry + dy[i];	
//				System.out.println();
//				System.out.println("현재 : "+arrx+","+arry);	
//				System.out.println("가려는곳 :" + nx+","+ny);	
				//System.out.println();
				//요정이동방법 - 같은 골렘 출구이거나 같은 골렘에서 움직이거나, 출구->다른골렘 
				if(!check(nx,ny)  || map[nx][ny]<=0 || visit[nx][ny])continue;
					
				if( (map[nx][ny] == map[arrx][arry]) || (map[nx][ny] == (map[arrx][arry] +1) ) || (map[arrx][arry]%2==0) ) {
			         q.offer(new int[]{nx, ny});
			         visit[nx][ny] = true;
			         //System.out.println(temp-2);
			         temp = Math.max(temp, nx);
			      }
				}
			
		}
		
		return temp;
		
	}
	private static boolean checkD(int x, int y) {
		int dx[] = {0,1,0}; 
		int dy[] = {1,0,-1};
		x = x+1;
		
		for(int i=0;i<3;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			//System.out.println(cnt+"째는 .."+nx+","+ny);
			
			if(!check(nx,ny)) {
				//System.out.println("바닥닿음 !!!!!!!!!!! ");
				return false;}
			
			if(map[nx][ny]!=0) return false;
			
		}
			
		return true;
		
	}
	private static boolean checkLR(char dir, int x, int y) {
		int dx[] = {-1,0,1,1,2}; 
		int dy[] = {1,2,2,1,1};
		
		if(dir=='L') {
			dx = new int[] {-1,0,1,1,2}; 
			dy = new int[]{-1,-2,-2,-1,-1};
		}
		
		for(int i=0;i<5;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//범위 벗어나거나 뭐가 들어있으면 안됌 
			if(!check(nx,ny) || map[nx][ny] !=0) return false;
		}
		return true;
	}


	private static void down(int x, int y, int id) {
		
		//전에꺼 없애기 
		int px[] = {0,-1,0}; 
		int py[] = {-1,0,1};
		
	
		for(int i=0;i<3;i++) {
			int nx = x + px[i];
			int ny = y + py[i];
			
			map[nx][ny]=0; 
			
		}
		
		//내려가
		int dx[] = {-1,0,1,0}; //북동남서 0123 방향 
		int dy[] = {0,1,0,-1};
		
		x=x+1; //행만 내려가
		
		map[x][y]= 2*id+1;  //정령 위치한 곳 
		
		for(int i=0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(end==i)map[nx][ny]= 2*id+2; //2부터 시작 2,3,4 ...
			else map[nx][ny]= 2*id+1; 
			
		}		
		
	}
	
	private static void rotateL(int x, int y,int id) {
		
		//전에꺼 없애기 
		int px[] = {0,-1,0}; 
		int py[] = {0,0,1};
		
	
		for(int i=0;i<3;i++) {
			int nx = x + px[i];
			int ny = y + py[i];
			
			map[nx][ny]=0; 
			
		}
		
		//내려가
		int dx[] = {-1,0,1,0}; //북동남서 0123 방향 
		int dy[] = {0,1,0,-1};
		
		x=x+1; 
		y=y-1;
		end =(end+3)%4;
		
		map[x][y]= 2*id+1;  //정령 위치한 곳 
		
		for(int i=0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(end==i)map[nx][ny]=2+2*id;  //출
			else map[nx][ny]=2*id+1;  //그냥 
			
		}

		
	}
	
	
	private static void rotateR(int x, int y, int id) {
		
		//전에꺼 없애기 
		int px[] = {0,-1,0}; 
		int py[] = {0,0,-1};
		
	
		for(int i=0;i<3;i++) {
			int nx = x + px[i];
			int ny = y + py[i];
			
			map[nx][ny]=0; 
			
		}
		
		//내려가
		int dx[] = {-1,0,1,0}; //북동남서 0123 방향 
		int dy[] = {0,1,0,-1};
		
		x=x+1; 
		y=y+1;
		end =(end+1)%4;
		
		map[x][y]= 2*id+1; ; //정령 위치한 곳 
		
		for(int i=0;i<4;i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(end==i)map[nx][ny]=2+2*id; 
			else map[nx][ny]=2*id+1; 
			
		}

		
	}
	private static void printMap() {
		//System.out.println(cnt+"번째 : ");
		for(int i=0;i<r+3;i++) {
			if(i==3)System.out.println("-----------");
			for(int j=0;j<c;j++) {
				
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	cnt++;
	}
	
	private static boolean check(int x, int y) {
		if(x<0||x>=r+3||y<0||y>=c) return false;
		return true;
		
	}
	private static void resetMap() {
		for(int i=0;i<r+3;i++) {
			for(int j=0;j<c;j++) {
				map[i][j] = 0;
				
			}
		}
	}
	
}

 

4. 얻은것

이문제에서 얻은게 증말 많다

일단 정리하자면 

1) 최단거리, 최장거리 등등 구하려면 BFS가 필수라는것 ..! 

2) BFS구현하려면 다음에 queue에 넣을 것, 지나칠것을 진짜 꼼꼼히 봐야함... ㅠㅠ

3) 삼성기출문제는 정신차리고 조건을 다 확인해봐야한다 .. 지난 코드도 다시보자 ^^

 

코드 짜는데는 2시간 남짓걸렸는데 BFS 구현 부분이 막히고,

왼쪽으로 내려갈때 열을 --; 해줘야하는데 ++; 하는 바람에 (새벽에 핫식스 먹고 정신 놓고 품)

디버깅 시간이 몇배는 더걸렸다 ... 

 

여튼 이문제에서는 밑에 함수 (BFS)가 가장 핵심!!!! 

다 풀어놓고 정답을 못구하면 억울하니깐..

요정은 같은 골렘 내에서 출구로 가거나, 같은 골램내라면 이동하거나, 현재 내가 있는 곳이 출구라면 visit하지 않은 곳이라면 어디든 갈수있다

 

다 구해서 Math.max() 함수로 가장 큰 row 값을 구해줘야함

	private static int moveSouth(int x, int y, int id) {
		int temp = 0;
		int[] dx= {1,-1,0,0};
		int[] dy= {0,0,-1,1};
		Queue<int[]> q = new LinkedList<>();
		boolean[][] visit = new boolean[r+3][c];
		
		q.offer(new int[] {x,y});
		temp = x;
		visit[x][y] = true;
		
		//System.out.println(x+","+y);
		
		while(!q.isEmpty()) {
			int[] arr = q.poll();
			int arrx = arr[0];
			int arry = arr[1];
			
			for(int i=0;i<4;i++ ) {
				int nx = arrx + dx[i];
				int ny = arry + dy[i];	
				//요정이동방법 - 같은 골렘 출구이거나 같은 골렘에서 움직이거나, 출구->다른골렘 
				if(!check(nx,ny)  || map[nx][ny]<=0 || visit[nx][ny])continue;
					
				if( (map[nx][ny] == map[arrx][arry]) || (map[nx][ny] == (map[arrx][arry] +1) ) || (map[arrx][arry]%2==0) ) {
			         q.offer(new int[]{nx, ny});
			         visit[nx][ny] = true;
			         //System.out.println(temp-2);
			         temp = Math.max(temp, nx);
			      }
				}
		}
		
		return temp;
		
	}