[Code Tree] 술래잡기(삼성 SW 역량테스트 2022 상반기 오전 1번 문제)

---

문제

술래잡기

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

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

 

---

풀이

• 해당 풀이에서 가장 중요한 부분은 술래의 이동을 제어하는 것 (순방향, 역방향)
• 또한 방향에 대해 정리를 해놓는 것을 중점으로 구현했다.
  • 순방향 : dxy -> 상 우 하 좌 (소용돌이 순방향)
  • 역방향 : rdxy -> 하 우 상 좌 (소용돌이 역방향)

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Pair {
	int x;
	int y;
	int d; // 방향 상좌하우 -> 0,1,2,3

	public Pair(int x, int y) {
		this.x = x;
		this.y = y;
		this.d = -1;
	}

	public Pair(int x, int y, int d) {
		this.x = x;
		this.y = y;
		this.d = d;
	}

	int getDistance(int x, int y){
		return Math.abs(x - this.x) + Math.abs(y - this.y);
	}
}
public class Main {


	static int N, M, H, K; 
	static int answer;
	static Pair[] thieves;
	static Pair[] trees;
	static Pair tagger;
	static int[][] dir;
	static int[][] dxy = {{-1,0},{0,1},{1,0},{0,-1}};
	static int[][] rdxy = {{1,0},{0,1},{-1,0},{0,-1}};
	public static void main(String[] args) throws IOException{
		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()); // 총 턴 횟수

		thieves = new Pair[M];
		trees = new Pair[H];

		answer = 0;

		// 술래는 가운데서 시작하고 
		// 도망자는 좌우로 이동하면 우, 상하로 이동하면 하 시작
		// 나무와 도망자는 초기에 겹쳐있을 수 있다.

		// 도망자 정보 
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			int tempX = Integer.parseInt(st.nextToken())-1;
			int tempY = Integer.parseInt(st.nextToken())-1;
			int tempD = Integer.parseInt(st.nextToken());

			if(tempD == 1) {
				tempD = 1; // 우
			}else if(tempD == 2) {
				tempD = 2; // 하
			}

			thieves[i] = new Pair(tempX, tempY, tempD);
		}

		// 나무 정보
		for(int i = 0; i < H; i++) {
			st = new StringTokenizer(br.readLine());
			trees[i] = new Pair(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1);
		}

		// 이제 술래 초기값 정해주고 바로 방향정해서 시뮬 돌리면 됨.
		tagger = new Pair(N/2, N/2, 0);

		simulation();

		System.out.println(answer);
	}

	static void simulation() {
		//술래는 소용돌이 방향으로 나가야함.
		// K번 만큼 진행
		int move = 1;
		int moveCnt = 0; // 2 가 될때마다 move를 1씩 올려줌
		int cnt = 0;
		dir = dxy;
		boolean rFlag = false;

		for(int t = 1; t <= K; t++) {
			moveThieves();

			int nx = tagger.x + dir[tagger.d][0];
			int ny = tagger.y + dir[tagger.d][1];

			tagger.x = nx;
			tagger.y = ny;
			
			cnt++;
			if(!rFlag && nx == 0 && ny == 0) {
				rFlag = true;
				dir = rdxy;
				tagger.d = 0;
				moveCnt = -1;
				cnt = 0;
				move = N-1;
			}

			else if(rFlag && nx == N/2 && ny == N/2) {
				rFlag = false;
				dir = dxy;
				tagger.d = 0;
				cnt = 0;
				moveCnt = 0;
				move = 1;
			}
			else {
				if(cnt == move) {
					cnt = 0;
					moveCnt++;
					tagger.d = (tagger.d+1) % 4;

					if(moveCnt == 2) {
						moveCnt = 0;
						if(rFlag) move -= 1;
						else move += 1;
					}
				}
			}





			countScore(t);

		}
	}	

	static void moveThieves() {
		for(int i = 0; i < M; i++) {
			if(thieves[i].d == -1) continue; // 잡힌 경우
			if(thieves[i].getDistance(tagger.x, tagger.y) > 3) continue;

			int curX = thieves[i].x;
			int curY = thieves[i].y;
			int curD = thieves[i].d;

			int nx = curX + dxy[curD][0];
			int ny = curY + dxy[curD][1];

			// 어쨋든 다음위치에 술래가 있어도 벗어나면 방향전환은 해줘야함.
			if(nx < 0 || ny < 0 || nx >= N || ny >= N) {
				thieves[i].d = (curD + 2) % 4;
				curD = thieves[i].d;

				nx = curX + dxy[curD][0];
				ny = curY + dxy[curD][1];
			}

			// 다음위치에 술래가 있다면
			if(tagger.getDistance(nx, ny) == 0) continue;

			// 술래가 없다면
			thieves[i].x = nx;
			thieves[i].y = ny;			
		}
	}

	static void countScore(int turn) {
		int curD = tagger.d;

		for(int i = 0; i < 3; i++) { // 술래의 시야는 언제나 3
			int nx = tagger.x + dir[curD][0] * i;
			int ny = tagger.y + dir[curD][1] * i;

			if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

			for(int j = 0; j < M; j++) { // 도망자 위치 체크
				if(thieves[j].d == -1) continue;

				if(thieves[j].getDistance(nx, ny) == 0 && !checkTreeHide(nx, ny)) {
					thieves[j].d = -1;
					answer += turn;
				}
			}
		}
	}

	static boolean checkTreeHide(int x, int y) {
		for(int i = 0; i < H; i++) {
			if(trees[i].x == x && trees[i].y == y) return true;
		}

		return false;
	}
}

 

- 구현시 실수(?) 때문에 조금 애를 먹었다. -> 술래의 방향은 dxy 와 rdxy 로 순방향과 역방향을 구별해놓고 정작 countScore 메서드에서 술래가 바라보는 방향에서는 dxy만 사용해서 rdxy 방향으로 술래가 이동할 때 정확한 방향에 대한 점수를 계산하지 못하게 구현이 되었었다. -> 찾는데 거의 2시간쓴듯... 

해당 메서드들의 구분은 아래와 같다.

 

메서드명	기능	비고
main	- 각종 static 변수들과 입력데이터를 전처리한다. - 또한 Pair 클래스 선언에 따른 각 객체를 인스턴스화하여 배열에 담는다. - 이후 simulation 메서드를 실행하고 최종적으로 answer를 출력한다.
simulation	- 전체 simulation을 진행한다.  - board 를 직접 그리는게 아닌 술래, 나무, 도망자 객체에 대한 좌표 계산 및 비교를 통해 풀이를 진행하게된다. - 실제 술래의 이동은 해당 메서드에서 각 turn에 따라 이동시킨다.
moveThieves	- 도망자 객체들을 배열에 담은 thieves 배열을 선언했다. - 해당 배열 내 저장된 Pair 객체들에 대한 이동을 수행한다.  - 문제에서 제시된 조건을 바탕으로 술래, 범위 등에 따라 이동하거나 방향을 바꾸는 과정을 포함한다.
countScore	- 술래의 이동이 끝나면 해당 술래가 바라보는 방향을 통해 점수를 구해야한다. - 해당 시점까지 이동한 술래, 도망자의 위치를 기반으로 나무의 위치를 따져 술래가 몇점을  가져갈 수 있는지 계산하고 술래가 도망자를 잡으면 도망자의 방향을 -1 로 처리하여 "잡힘" 처리한다.
checkTreeHide	- 나무의 위치는 고정되어 있다.  - 따라서 해당 나무들의 위치를 인자로 들어온 x, y 좌표와 비교하여 나무와 위치가 같은지 아닌지를 boolean 값으로 반환한다.	- 사실 나무의 위치는 고정되어있기 때문에 board상에 그냥 위치를 박아놔도 되었을 법하다.  - board의 타입은 boolean으로 하면 H 최대 10000개에 대한 반복문을 배열 값 참조로 줄일 수 있을 것.

 

가장 중요하다고 생각되는 로직은 아래 코드에 있는 술래의 이동이다.

 

    //술래는 소용돌이 방향으로 나가야함.
    // K번 만큼 진행
    int move = 1;
    int moveCnt = 0; // 2 가 될때마다 move를 1씩 올려줌
    int cnt = 0;
    dir = dxy;
    boolean rFlag = false;

    for(int t = 1; t <= K; t++) {
        moveThieves();

        int nx = tagger.x + dir[tagger.d][0];
        int ny = tagger.y + dir[tagger.d][1];

        tagger.x = nx;
        tagger.y = ny;

        cnt++;
        if(!rFlag && nx == 0 && ny == 0) {
            rFlag = true;
            dir = rdxy;
            tagger.d = 0;
            moveCnt = -1;
            cnt = 0;
            move = N-1;
        }

        else if(rFlag && nx == N/2 && ny == N/2) {
            rFlag = false;
            dir = dxy;
            tagger.d = 0;
            cnt = 0;
            moveCnt = 0;
            move = 1;
        }
        else {
            if(cnt == move) {
                cnt = 0;
                moveCnt++;
                tagger.d = (tagger.d+1) % 4;

                if(moveCnt == 2) {
                    moveCnt = 0;
                    if(rFlag) move -= 1;
                    else move += 1;
                }
            }
        }

        countScore(t);

    }

- 초기 move, moveCnt, cnt 를 선언한다. 각각의 역할은 다음과 같다.

  - move : 현재 술래가 이동할 수 있는 최대값 (현재 방향으로)

  - moveCnt : 소용돌이의 특성상 (순방향기준) 상, 우, 하, 좌 이동이 1, 1, 2,2, 3,3,4,4 ... 식으로 두번씩 반복된다. 이때, 2번 이동했는지 제어를 위해 사용되는 변수이다. 

  - cnt : move의 값은 현재 술래가 이동할 수 있는 최댓값이라면 현재 술래가 몇 칸 이동했는지에 대한 값이 필요하다. 그 값을 저장하기 위한 변수이다. 

- 소용돌이 움직임(순방향) 은 아래를 확인해보자

순방향 소용돌이 움직임, N=5 인경우

- 순방향으로 움직일 때 술래는 위부터 시작하고 상 -> 우 -> 하 -> 좌 방향전환을 반복한다. 

- 여기서 주목할 부분은 마지막 즉 N과 같은 값이 되는 마지막 이동의 경우에는 5만큼 이동하면 정해진 구역을 벗어나게 된다. 따라서 우리는 해당 부분을 제어해줘야하고 위 코드에 아래와 같은 제어문이 추가된다. 

  if(!rFlag && nx == 0 && ny == 0) {
            rFlag = true;
            dir = rdxy;
            tagger.d = 0;
            moveCnt = -1;
            cnt = 0;
            move = N-1;
        }

- rFlag는 (reverseFlag) false일 때 순방향으로 이동하고 있음을 뜻한다. 

- 해당 부분에서 범위를 벗어나기전에 마지막으로 술래가 이동하는 좌표가 0,0 이라면 rFlag를 true로 바꿔주고 이후 dir 재설정해준다. 

- cnt는 역방향으로 다시 세줘야해서 0으로 설정하고, move 값의 경우에는 N-1 로 설정해준다.(moveCnt에서 설명추가)

- 해당 코드에서 가장 중요한 부분은 moveCnt 를 -1로 설정하는 부분이다. 

  - moveCnt를 -1로 설정하는 이유는 0,0 좌표위치에서 술래의 움직임이 끝나면 되돌아갈때 기존 1,1,2,2,3,3,4,4,... 로 순방향이동을 했다고 돌아갈때에도 마찬가지로 4,4,3,3,2,2,1,1 을 해야할 순 없다. 아래 그림을 보자

역방향 움직임, N=5 인 경우

- 역방향의 경우에는 0,0 부터 시작해 N-1 만큼 3번 움직이고 그 다음 2회씩 반복된다. 

- 따라서 역방향으로 방향전환을 할 때 초기에는 moveCnt = -1로 값을 설정하고 이후 else 문에서 방향전환을 할 때에는 다시 moveCnt = 0으로 해주는 것을 통해 역방향 출발후 N-1 만큼 총 3번 움직이고 move 값을 줄이도록 구현했다. 

 

	if(!rFlag && nx == 0 && ny == 0) {
            rFlag = true;
            dir = rdxy;
            tagger.d = 0;
            moveCnt = -1;
            cnt = 0;
            move = N-1;
        }

        else if(rFlag && nx == N/2 && ny == N/2) {
            rFlag = false;
            dir = dxy;
            tagger.d = 0;
            cnt = 0;
            moveCnt = 0;
            move = 1;
        }
        else {
            if(cnt == move) {
                cnt = 0;
                moveCnt++;
                tagger.d = (tagger.d+1) % 4;

                if(moveCnt == 2) {
                    moveCnt = 0;
                    if(rFlag) move -= 1;
                    else move += 1;
                }
            }
        }

- 그리고 다시 중심점으로 돌아가면 초기 설정했던 대로 rFlag는 false, dir 방향을 순방향으로 설정하고 cnt, moveCnt, move 값을 초기 설정했던 값들록 설정해주면 많은 횟수일지라도 술래는 순방향, 역방향 움직임을 반복할 수 있다.

 

+) 설명이 충분한지 모르겠네요... ㅠ