[백준, 17780, 자바] 새로운 게임

https://www.acmicpc.net/problem/17780

17780번: 새로운 게임

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하

www.acmicpc.net

1. 문제 핵심

흰색, 파란색, 빨간색 자리 별로 이동이 다르다.
외곽은 파란색과 동일한 타일 취급한다.
최대 1000번까지 루프를 반복하며 그 이상은 -1을 출력한다.

2. 문제 접근

말의 자리와 쌓여있는 높이를 수월히 계산하기 위해서 보드와 해당 보드 칸에 쌓여있는 말의 번호를 저장하는 3차원 배열이 존재하고 각 말들이 어느 행, 열의 칸에 몇 번째 레벨에 쌓여있는지 저장하는 2차원 배열로 관리한다.
흰색, 파란색, 빨간색 각각 연산을 수행하되 파란색일 때는 방향을 180도 전환하고 한 칸 전진했을 때 흰색, 빨간색 연산과 동일한 연산을 수행하게끔 한다.

3. 문제 후기

문제 자체는 구현이기 때문에 어렵진 않지만 오랫만에 구현 문제를 풀다보니 자잘한 실수로 디버깅에 오랜 시간이 걸렸다. 구현 문제는 꾸준히 풀면서 어떤 실수를 자주 하는지 파악하는 것이 중요하다고 생각했다.

자바코드

package _0707.ChungLee;

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

public class BOJ_17780_G2_새로운게임 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[][] dydx = new int[][] { {}, { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } };
		// 0:보드 상태, 1:최대높이, 2~K+1:저장된 말
		int[][][] bd = new int[N + 2][N + 2][K + 2];
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				bd[i][j][1] = 2;
			}
		}
		int[][] horse = new int[K + 1][4];
		for (int i = 0; i < N + 2; i++) {
			if (i == 0 || i == N + 1) {
				for (int j = 0; j < N + 2; j++) {
					bd[i][j][0] = 2;
				}
				continue;
			}

			st = new StringTokenizer(br.readLine());

			for (int j = 0; j < N + 2; j++) {
				if (j == 0 || j == N + 1) {
					bd[i][j][0] = 2;
					continue;
				}

				bd[i][j][0] = Integer.parseInt(st.nextToken());
			}
		}

		for (int i = 1; i <= K; i++) {
			st = new StringTokenizer(br.readLine());
			// 행
			horse[i][0] = Integer.parseInt(st.nextToken());
			// 열
			horse[i][1] = Integer.parseInt(st.nextToken());
			// 이동방향
			horse[i][2] = Integer.parseInt(st.nextToken());
			// 몇 번째 높이인지 확인, 최소 0, 최대 k-1
			horse[i][3] = bd[horse[i][0]][horse[i][1]][1];
			bd[horse[i][0]][horse[i][1]][bd[horse[i][0]][horse[i][1]][1]++] = i;

		}
		int dir, crntY, crntX, nextY, nextX, nextBdColor, nextBdStack, crntBdStack, changeHorseNum;
		for (int CNT = 1; CNT <= 1000; CNT++) {
			for (int i = 1; i <= K; i++) {
				// 가장 아래있는 말이 아니면 이동 불가
				if (horse[i][3] != 2)
					continue;
				// 현재 말의 방향
				dir = horse[i][2];

				crntY = horse[i][0];
				crntX = horse[i][1];
				nextY = horse[i][0] + dydx[dir][0];
				nextX = horse[i][1] + dydx[dir][1];

				nextBdColor = bd[nextY][nextX][0];
				crntBdStack = bd[horse[i][0]][horse[i][1]][1];
				nextBdStack = bd[nextY][nextX][1];

				// 흰색
				if (nextBdColor == 0) {
					// 1. 말 상태 저장 배열을 최신화
					// 2.
					for (int j = 2; j < crntBdStack; j++) {

						changeHorseNum = bd[crntY][crntX][j];

						// 다음 보드에 이전 보드 말들을 쌓아올림
						bd[nextY][nextX][nextBdStack] = changeHorseNum;

						// 옮긴 말들의 현재 위치를 최신화
						horse[changeHorseNum][3] = nextBdStack;
						nextBdStack++;

						// 해당 말의 현재 좌표 최신화
						horse[changeHorseNum][0] = nextY;
						horse[changeHorseNum][1] = nextX;

						// 해당 말의 이전 위치 삭제
						bd[crntY][crntX][j] = 0;
						// 쌓인 말이 4개 이상인 경우 종료
						if (nextBdStack >= 6) {
							System.out.println(CNT);
							return;
						}
					}

					// 다음 칸은 말이 추가되었기 때문에 해당 값으로 최신화
					bd[nextY][nextX][1] = nextBdStack;

					// 옮긴 후 이전 위치 초기화
					bd[crntY][crntX][1] = 2;
				}
				// 빨간색
				else if (nextBdColor == 1) {
					// 흰 타일과 다르게 쌓이는 순서가 반대
					for (int j = crntBdStack - 1; j >= 2; j--) {
						changeHorseNum = bd[crntY][crntX][j];

						bd[nextY][nextX][nextBdStack] = bd[crntY][crntX][j];
						horse[changeHorseNum][3] = nextBdStack;
						nextBdStack++;

						// 해당 말의 현재 좌표 최신화
						horse[changeHorseNum][0] = nextY;
						horse[changeHorseNum][1] = nextX;

						// 해당 말의 이전 위치 삭제
						bd[crntY][crntX][j] = 0;

						// 쌓인 말이 4개 이상인 경우 종료
						if (nextBdStack >= 6) {
							System.out.println(CNT);
							return;
						}
					}

					// 다음 칸은 말이 추가되었기 때문에 해당 값으로 최신화
					bd[nextY][nextX][1] = nextBdStack;

					// 옮긴 후 이전 노드의 카운트 초기화
					bd[crntY][crntX][1] = 2;
				}
				// 파란색
				else {
					// 1:우,2:좌,3:상,4:하
					if (horse[i][2] == 1)
						horse[i][2] = 2;
					else if (horse[i][2] == 2)
						horse[i][2] = 1;
					else if (horse[i][2] == 3)
						horse[i][2] = 4;
					else
						horse[i][2] = 3;
					
					dir = horse[i][2];

					crntY = horse[i][0];
					crntX = horse[i][1];
					nextY = horse[i][0] + dydx[dir][0];
					nextX = horse[i][1] + dydx[dir][1];


					crntBdStack = bd[horse[i][0]][horse[i][1]][1];
					nextBdStack = bd[nextY][nextX][1];
					// 다음 칸이 흰색일 때
					if (bd[nextY][nextX][0] == 0) {
						// 1. 말 상태 저장 배열을 최신화
						// 2.
						for (int j = 2; j < crntBdStack; j++) {

							changeHorseNum = bd[crntY][crntX][j];

							// 다음 보드에 이전 보드 말들을 쌓아올림
							bd[nextY][nextX][nextBdStack] = changeHorseNum;

							// 옮긴 말들의 현재 위치를 최신화
							horse[changeHorseNum][3] = nextBdStack;
							nextBdStack++;

							// 해당 말의 현재 좌표 최신화
							horse[changeHorseNum][0] = nextY;
							horse[changeHorseNum][1] = nextX;

							// 해당 말의 이전 위치 삭제
							bd[crntY][crntX][j] = 0;
							// 쌓인 말이 4개 이상인 경우 종료
							if (nextBdStack >= 6) {
								System.out.println(CNT);
								return;
							}
						}

						// 다음 칸은 말이 추가되었기 때문에 해당 값으로 최신화
						bd[nextY][nextX][1] = nextBdStack;

						// 옮긴 후 이전 위치 초기화
						bd[crntY][crntX][1] = 2;
					}
					// 다음 칸이 빨간색일 때
					else if (bd[nextY][nextX][0] == 1) {
						// 흰 타일과 다르게 쌓이는 순서가 반대
						for (int j = crntBdStack - 1; j >= 2; j--) {
							changeHorseNum = bd[crntY][crntX][j];

							bd[nextY][nextX][nextBdStack] = bd[crntY][crntX][j];
							horse[changeHorseNum][3] = nextBdStack;
							nextBdStack++;

							// 해당 말의 현재 좌표 최신화
							horse[changeHorseNum][0] = nextY;
							horse[changeHorseNum][1] = nextX;

							// 해당 말의 이전 위치 삭제
							bd[crntY][crntX][j] = 0;

							// 쌓인 말이 4개 이상인 경우 종료
							if (nextBdStack >= 6) {
								System.out.println(CNT);
								return;
							}
						}

						// 다음 칸은 말이 추가되었기 때문에 해당 값으로 최신화
						bd[nextY][nextX][1] = nextBdStack;

						// 옮긴 후 이전 노드의 카운트 초기화
						bd[crntY][crntX][1] = 2;
					}
				}
			}
		}
		System.out.println(-1);
	}
}

'programming > 알고리즘' 카테고리의 다른 글

[백준, 1027, 자바] 고층 건물 (0)	2022.07.25
[백준, 23791, 자바] K번째 음식 찾기 1 (0)	2022.07.07
[프로그래머스, 자바] 여행경로 (0)	2022.06.30
[프로그래머스, 자바] 징검다리 (0)	2022.06.30
[백준, 3954, 자바] Brainf**k 인터프리터 (0)	2022.06.22

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

코딩은 재밌게, 기록은 꾸준히

[백준, 17780, 자바] 새로운 게임

1. 문제 핵심

2. 문제 접근

3. 문제 후기

'programming > 알고리즘' 카테고리의 다른 글

댓글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

[백준, 17780, 자바] 새로운 게임

1. 문제 핵심

2. 문제 접근

3. 문제 후기

'programming > 알고리즘' 카테고리의 다른 글

관련글

댓글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역