코드 트리 - 술래잡기(44번)

❓ 문제 - 코드 트리(code tree) 술래잡기 44번 - JAVA 풀이법

 

출처

(https://www.codetree.ai/frequent-problems/hide-and-seek/description)

코드트리

 

 

📝 문제해결법

1. 문제

• 1회 안에 술래와의 거리가 3이하인 도망자들이 도망을 다니고 그 다음에 술래가 해당하는 방향에 맞춰 한 칸 이동한 후 시야가 3이하인 술래들을 잡을 수 있다. 이때 k번 술래의 이동동안 획득되는 점수를 구하여라.

 

2. 해결 방법

• 우선 5 <= n <= 99, 1 <= m, h <= n^2 이고 문제에서 주어진 조건대로 로직을 돌렸을 때 얻어지는 값을 구해야하므로 전형적인 시뮬레이션 문제이다.
• 1번의 이동은 술래와 거리가 3이하인 도망자들의 도망 -> 술래가 달팽이 모양으로 한 칸 이동 -> 현재 보는 시야에서 자신이 포함하는 위치를 포함하여 거리가 3이하인 술래를 잡기가 이면 이것에 맞춰 일단 k번 이동 시키면 된다.
• 술래는 도망자를 기준으로 거리를 구해야하고, 도망자는 특정 이동 방향을 갖고 있으므로 ArrayList<Integer>의 2차원 배열 통해 도망자의 좌표 x, y 뿐만 아니라 방향에 대한 정보도 저장한다. -> 도망자는 이동하다가 한 영역에 여러 명이 존재할 수 있기 때문에 ArrayList를 활용한다.
•  그리고 도망자가 이동할 때 한번에 이동된 후의 정보를 다른 ArrayList<Integer>[][]에 저장해뒀다가 한 번에 원래의 도망자의 위치를 기록하는 ArrayList<Integer>[][]에 다시 복사해준다.
• 도망자가 도망갈 때 유의해야 하는 점은 주어진 문제의 조건이며, 이것을 잘 고려해서 구현에 적용해야한다.
  • 도망자가 우선 술래와의 거리가 3초과라면 현재 자신이 있는 위치에 그대로 다시 존재해야 한다.
  • 도망자가 술래와의 거리가 3이하라면
    • 자신의 방향에 맞추어 이동할 때 격자를 넘어가는 범위라면 상->하, 하->상, 좌->우, 우->좌로 방향 전환을 시켜주고 만약 방향 전환 시켜주고 한 칸을 이동할 때 술래가 없다면 그 곳으로 이동 처리해준다.
    • 만약 격자도 벗어나서 방향 전환 후 한 칸을 이동할 곳에 술래가 있다면 이동 처리 없이 원래 있는 위치에 방향만 바꿔서 값을 저장한다.
    • 만약 격자를 넘어가지 않고 이동방향에 맞춰 이동하려는데 술래가 있다면 그자리에 있고, 술래가 없다면 이동처리 해서 값을 저장한다.
• 술래의 이동이다.
  • 술래는 달팽이 모양으로 이동하는데 밑에서 시야를 기준으로 술래를 잡기 때문에 이 부분을 잘 구현해야하는 것이 특징이다. 
  • 그리고 이 문제의 특별한 점은 달팽이로 움직이고 1,1 의 위치에서 다시 반대 방향으로 중앙 위치로 돌아오는 특징이 있다. 이런 방향에 대한 것을 원래 방향으로 움직일 때의 방향 정보를 c_map1, 반대 방향으로 돌아올 때의 방향 정보를 c_map2로 저장하여 해당 방향 정보를 기준으로 이동 처리 및 도망자를 잡는데 방향을 활용한다.

• 중앙(n/2+1, n/2+1) 위치에서 달팽이 이동이 시작될 때 방향의 변환은 규칙적으로 상(0) -> 우(1) -> 하(2) -> 좌(3)로 이루어진다.
• 방향의 전환은 상->우->하->좌를 반복하면서 1, 1, 2, 2, 3, 3, 4, 4, ..., n 칸씩 각 방향에 맞춰 이동했을 때 방향 전환이 이루어진다. 이것을 이중 while문을 통해서 이동 칸수를 count하면서 방향 전환을 시켜주고 방향에 대한 정보를 2차원 배열에 저장한다.
• 반대 방향으로 돌아올 때는 방향을 구하면 기존에 이동방향에 반대로, 상(0)->하(2), 하(2)->상(0), 우(1)->좌(3), 좌(3)->우(1) 이므로 이것을 처리해서 c_map1를 구할 때 동시에 c_map2를 구한다.
• c_map2를 구할 때 유의할 점은 c_map1에서 달팽이를 돌다가 빨간 화살표처럼 방향을 바꾸는 위치에서는 기존 방향의 반대가 아닌, 상(0)->우(1), 우(1)->하(2), 하(2)->좌(3), 좌(3)->상(0)로 변환 처리 한다.
• 그리고 c_map1이든 c_map2이든 1,1과 중앙(n/2+1, n/2+1)의 이동방향은 같기 때문에 하(2), 상(0)로 지정해둬야 한다. 
• 그리고 k번 이동하면서 이동처리를 위해 1,1에 도착했을 때 turn을 true로 바꾸고, 중앙(n/2+1, n/2+1)로 도착했을 때 turn의 값을 false로 바꿔서, turn이 false일 때는 c_map1 사용하고, turn이 true일 땐 c_map2를 사용하도록 구현했다.

• 술래가 바라보는 시야로 도망자 잡기
  • c_map1과 c_map2를 활용해서 현재 바라보는 시야로 현재 위치를 기준으로 거리가 3이하에 있는 몬스터를 잡도록 구현한다.
  • 몬스터가 만약 트리와 같이 있지 않고 거리가 3이하에 있다면 몬스터의 숫자를 카운터 해주고 몬스터를 clear해줘서 잡도록 한다.
  • 그리고 점수를 증가시킬 때는 현재 진행중인 이동 숫자 p * 잡은 몬스터 수를 더해주면서 갱신해준다.

 

3. 느낀점

• 상반기때 하나의 예외케이스를 처리 못해서..코테 광탈한 문제 ㅠㅠ
• 코드트리로 그래도 5시간동안 다시 그 때의 잘못을 짚어가면서 풀었더니 그래도 해결되었다..
• 그 때 이런식으로 빡구현하는 게 맞는 건가 의문이 들었는데.. 그게 맞았다
• 앞으로 이런 빡구현할 때 더 상황에 대해 나눠서 구현 계획을 세워야겠다..

 

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_44 {


	public static int[] dx = {0, 0, 1, -1};
	public static int[] dy = {1, -1, 0, 0};
	
	public static int[] c_dx = {-1, 0, 1, 0};
	public static int[] c_dy = {0, 1, 0, -1};
	
	public static int[][] c_map1;
	public static int[][] c_map2;
	public static int n, m, h, k;
	public static ArrayList<Integer>[][] m_map;
	public static boolean[][] tree;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
	
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		h = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		boolean turn = false;
		m_map = new ArrayList[n+1][n+1];
		c_map1 = new int[n+1][n+1];
		c_map2 = new int[n+1][n+1];
		tree = new boolean[n+1][n+1];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				m_map[i][j] = new ArrayList<Integer>();
			}
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			
			if(dir==1){
				m_map[x][y].add(0);
			} else {
				m_map[x][y].add(2);
			}
		}
		
		for(int i=0;i<h;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			tree[x][y] = true;
		}
		
		int nx = n/2 +1;
		int ny = n/2 +1;
		int d = 0;
		int num = 1;
		outer: while(true) {
			int cnt = 0;
			int same_cnt = 0;
			while(true) {
				nx += c_dx[d];
				ny += c_dy[d];
				c_map1[nx][ny] = d;
				c_map2[nx][ny] = (d+2)%4;
				cnt++;
				if(cnt == num) {
					d = (d+1) % 4;
					c_map1[nx][ny] = d;
					c_map2[nx][ny] = (d+1)%4;
					cnt = 0;
					if(num == n) {
						break outer;
					}
					if(same_cnt == 0) {
						same_cnt++;
					} else {
						num++;
						same_cnt = 0;
						break;
					}
				} 
			}
		}
		
		c_map1[1][1] = 2;
		c_map2[1][1] = 2;
		
		int x = n/2 + 1;
		int y = n/2 + 1;
		int dir = 0;
		int sum = 0;
		for(int p=1;p<=k;p++) {

			// 도망자 이동
			ArrayList[][] monster = new ArrayList[n+1][n+1];
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					monster[i][j] = new ArrayList<Integer>();
				}
			}
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					if(m_map[i][j].size() == 0) continue;
					for(int n_d:m_map[i][j]) {
						if(Math.abs(i-x) + Math.abs(j-y) <= 3) {
							// 1칸 이동 -> 격자
							int ni = i + dx[n_d];
							int nj = j + dy[n_d];
								
							if(ni < 1 || ni > n || nj < 1 || nj > n) {
								if(n_d % 2 == 0) {
									n_d++;
								} else {
									n_d--;
								}
								
								if(x != ni+dx[n_d] || y != nj+dy[n_d]) {
									ni = i + dx[n_d];
									nj = j + dy[n_d];
								} 
							} 
							if(x != ni || y != nj) {
								monster[ni][nj].add(n_d);
							} else {
								monster[i][j].add(n_d);
							}
						
						} else {
							monster[i][j].add(n_d);
						}
					}
					
				}
			}
			for(int i=1;i<=n;i++) {
				for(int j=1;j<=n;j++) {
					m_map[i][j] = monster[i][j];
				}
			}
			
			
			if(!turn) {
				dir = c_map1[x][y];
				x += c_dx[dir];
				y += c_dy[dir];
				dir = c_map1[x][y];
			} else {
				dir = c_map2[x][y];
				x += c_dx[dir];
				y += c_dy[dir];
				dir = c_map2[x][y];
			}
			if((x == 1 && y == 1) || (x == (n/2+1) && y == (n/2+1))) {
				turn = turn?false:true;
			}
			//System.out.println(dir+" "+x+" "+y);
			int count = 0;
			// 점수 획득
			for(int s=0;s<=2;s++) {
				int s_x = x + c_dx[dir] * s;
				int s_y = y + c_dy[dir] * s;
				if(s_x < 1 || s_x > n || s_y < 1 || s_y > n) continue;
				if(m_map[s_x][s_y].size() != 0 && !tree[s_x][s_y]) {
					count += m_map[s_x][s_y].size();
					m_map[s_x][s_y].clear();
					
				}
			}
			sum += (p*count);
		}
		
		System.out.println(sum);
		
	}
}