구름톤 챌린지 2주 Day5 - GameJam

GameJam (Java)

 

제출한 답 :

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        
        int N = scanner.nextInt();
        int[][] start = new int[2][2];
        for (int i = 0; i < 2; i++) {
            start[i][0] = scanner.nextInt() - 1;
            start[i][1] = scanner.nextInt() - 1;
        }
        
        String[][] gradle = new String[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                gradle[i][j] = scanner.next();
            }
        }
        
        int goorm = search(start[0][0], start[0][1], gradle, N);
        int player = search(start[1][0], start[1][1], gradle, N);
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if (goorm > player) {
            bw.write("goorm " + goorm);
        } else {
            bw.write("player " + player);
        }
        bw.flush();
        bw.close();
    }

    static int search(int r, int c, String[][] gradle, int N) {
        int result = 1;
        boolean[][] visited = new boolean[N][N];
        visited[r][c] = true;
        while (true) {
            int move = Integer.parseInt(gradle[r][c].substring(0, gradle[r][c].length() - 1));
            char dir = gradle[r][c].charAt(gradle[r][c].length() - 1);
            for (int i = 0; i < move; i++) {
                if (dir == 'U') {
                    r = r - 1 < 0 ? N - 1 : r - 1;
                } else if (dir == 'D') {
                    r = r + 1 == N ? 0 : r + 1;
                } else if (dir == 'L') {
                    c = c - 1 < 0 ? N - 1 : c - 1;
                } else {
                    c = c + 1 == N ? 0 : c + 1;
                }
                if (visited[r][c]) {
                    return result;
                }
                result++;
                visited[r][c] = true;
            }
        }
    }
}

마무리 문제 

이거 다음 부터는 시간이 없어서 못 풀거 같았는데 진짜 못 풀었네..;;

솔직히 이것도 잘 이해가 안 됨ㅋㅋㅋ  

예시 하나는 맞는데 예시 하나가 계속 틀려서 결국 포기..문제를 푼건지 만건지

나중에 이 문제를 보고 이렇게 쉬운 문제를 왜 못 풀었는지 회고할 수 있었으면 좋겠다.

 

문제 풀이

필요한 개념

• 시뮬레이션

분석

GameJam 문제는 폭탄 구현하기 (2)와 비슷한 문제이지만, 조금 더 어렵습니다. 규칙은 단순하지만, 규칙의 특성과 모든 조건을 따지면서, 구현하는 능력이 필요합니다.

또한, 등장하는 2개의 캐릭터의 이동하는 논리는 동일합니다. 즉 각각 캐릭터에 대해서 구현하기 보다는 함수를 통해서 간결하게 구현하는 능력도 요구하고 있습니다.

이동 방법을 살펴보면, 3R 이라면 오른쪽으로 3칸 이동하라는 의미가 입니다. 단, 이동할 때 보드의 범위를 밖으로 나간다면, 반대쪽 첫 번째 칸으로 이동한다는 조건의 구현이 필요해요.

이동의 종료는 캐릭터가 방문했던 칸에 다시 방문하면 이동을 종료합니다. 이때 캐릭터의 점수는 방문했던 칸의 개수를 알아내야 합니다.

문제풀이

구현 문제는 특별한 알고리즘을 요구하지 않습니다. 우선, 게임의 규칙을 정확하게 파악할 필요가 있습니다.

• 캐릭터는 현재 위치에서, 명령에 따라 <command> 방향으로 <count> 칸만큼 움직인다.
• 캐릭터가 명령 수행 중에, 보드의 밖으로 이동할 경우, 반대편으로 이동한다.
• 캐릭터가 이미 방문한 칸을 지나거나, 다시 방문하는 경우 게임은 끝난다.
• 캐릭터가 방문한 칸의 개수가 게임에서 얻은 점수이다.

위의 요구 사항을 꼼꼼하게 구현할 수 있다면, 문제 자체는 어렵지 않게 해결할 수 있습니다.

데이터 입력

문제에서 입력이 들어오는 데이터는 간단하지만, 시뮬레이션을 위해서 필요한 데이터와 변수를 미리 선언해야 합니다.

• board
• 캐릭터들이 이동하는 게임 판
• {-}Visited
• 각각 캐릭터의 방문 지점 관리를 위한 변수
• {-}Pos, {-}score
• 각각 캐릭터들의 시작 위치와, 점수

이후에 입력되는 데이터를 각각 할당하면 됩니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
				// borad 게임의 크기
        N = scanner.nextInt();
				
				// 구르미와 플레이어의 시작 위치, 방문 지점
				int[] goormPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
				boolean[][] goormVisited = new boolean[N][N];
				int[] playerPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
				boolean[][] playerVisited = new boolean[N][N];

				// 보드 게임 판
        board = new String[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                board[i][j] = scanner.next();
            }
        }
				// 입력 종료
        scanner.close();
    }
}

방향관리 Map

행렬에서 방향을 관리할 경우, dx/dy 기법을 사용하고 있습니다.

이는 인덱스로 찾아가는 방향이지만, 이번 문제처럼 방향이 문자 형태로 주어진다면 Map을 사용하는 것이 좋습니다.

U 명령이 주어졌을 때, 바로 방향을 불러올 수 있도록 아래와 같이 명령에 방향을 할당하면 됩니다.

import java.util.*;

public class Main {
    static HashMap<String, int[]> directions = new HashMap<String, int[]>() {
		{
			put("U", new int[]{-1, 0});
			put("D", new int[]{1, 0});
			put("L", new int[]{0, -1});
			put("R", new int[]{0, 1});
		}
	};

    public static void main(String[] args) {
				..code
		}
}

좌표 재 위치

이동 조건 중 보드의 범위 밖으로 나갔을 때, 좌표를 반대쪽 첫 번째 칸으로 조건이 있습니다.

간단하게 생각하면 좌표가 외부로 나갔을 시점에 초기화를 하면 됩니다. -1 이 되었을 때, N-1 로 변환하고, N 이 되었을 때, 0 으로 바꿔주는 setPos() 함수를 아래처럼 만들 수 있습니다.

public static int setPos(int a) {
        if (a == -1) return N - 1;
        if (a == N) return 0;
        return a;
    }

시뮬레이션

시뮬레이션을 위한 데이터와 이동에 필요한 기능을 모두 구현했기 때문에, 말 그대로 직접 구현하면 됩니다. 이 시뮬레이션의 종료 조건은 캐릭터가 방문했던 지점에 다시 방문하면 시뮬레이션이 종료됩니다.

방문 지점을 관리하는 Visited[x][y] 의 값이 true 라면 시뮬레이션이 종료된다고 생각하면 됩니다. 또한 플레이어와 구름이라는 2개의 캐릭터가 존재하기 때문에 함수로 구현하면 코드의 길이가 짧아지고 가독성이 좋아집니다.

아래의 코드보다 더 효율적이거나, 간결하게 작성할 수 있습니다. 다만, 이런 시뮬레이션 문제의 특징은 무엇을 구현해야 하는지 명확히 해야, 실수의 여지가 줄어든다는 점입니다.

/*
Pos = 캐릭터의 시작 위치
Vistied = 방문 지점
Score = 반환할 점수
borad = 게임판
*/
public static int move(int[] pos, boolean[][] visited, int score, String[][] board, int N) {
			int x = pos[0];
			int y = pos[1];
			// 방문 위치를 true로 전환
			visited[x][y] = true;
			// flag = 시뮬레이션이 진행될 수 있는지 판단
			// true : 시뮬레이션 가능, false : 시뮬레이션 종료
			boolean flag = true;

			while (flag) {
			// 현재 위치한 칸의 이동 명령을 분리
			String command = board[x][y];
			int distance = Integer.parseInt(command.substring(0, command.length() - 1));
            String direction = command.substring(command.length() - 1);
			// distance 칸만큼 direction 방향으로 이동합니다.
               for (int i = 0; i < distance; i++) {
							x += directions.get(direction)[0];
							y += directions.get(direction)[1];
							x = set_Pos(x, N);
							y = set_Pos(y, N);

							/* 
							방문 가능 여부를 파악
							visited[x][y] 의 값이 false 라면 시뮬레이션 진행
								Score + 1, visited[x][y] = true 갱신
							visited[x][y] 의 값이 true 라면 시뮬레이션 flag종료
								flag = false 로 갱신
							*/	
							if (!visited[x][y]) {
									visited[x][y] = true;
									score += 1;
							} else {
									flag = false;
									break;
							}
					}
			}
			// 점수를 반환한다.
			return score;
	}

위의 함수를 통해서 우리는 구름이와 플레이어의 점수를 바로 구할 수 있습니다.

import java.util.Scanner;
import java.util.HashMap;

public class Main {
		..code Directions, set_Pos(), Move() 함수 구현 부

    public static void main(String[] args) {
				..code 데이터 입력 부분
	
        int groomScore = move(goormPos, goormVisited, 1);
        int playerScore = move(playerPos, playerVisited, 1);

        if (groomScore > playerScore) {
            System.out.println("goorm " + groomScore);
        } else if (groomScore < playerScore) {
            System.out.println("player " + playerScore);
        }

        scanner.close();
    }
}

 

답 :

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] goormPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
		boolean[][] goormVisited = new boolean[N][N];
		int[] playerPos = {scanner.nextInt() - 1, scanner.nextInt() - 1};
		boolean[][] playerVisited = new boolean[N][N];

		String[][] board = new String[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				board[i][j] = scanner.next();
			}
		}

		int goormScore = move(goormPos, goormVisited, 1, board, N);
		int playerScore = move(playerPos, playerVisited, 1, board, N);

		if (goormScore > playerScore) {
			System.out.println("goorm " + goormScore);
		} else if (goormScore < playerScore) {
			System.out.println("player " + playerScore);
		}
		scanner.close();
	}


	public static int set_Pos(int a, int N) {
			if (a == -1) return N - 1;
			if (a == N) return 0;
			return a;
	}
	
	static HashMap<String, int[]> directions = new HashMap<String, int[]>() {
		{
			put("U", new int[]{-1, 0});
			put("D", new int[]{1, 0});
			put("L", new int[]{0, -1});
			put("R", new int[]{0, 1});
		}
	};

	public static int move(int[] pos, boolean[][] visited, int score, String[][] board, int N) {
			int x = pos[0];
			int y = pos[1];
			visited[x][y] = true;
			boolean flag = true;

			while (flag) {
					String command = board[x][y];
					int distance = Integer.parseInt(command.substring(0, command.length() - 1));
					String direction = command.substring(command.length() - 1);

					for (int i = 0; i < distance; i++) {
							x += directions.get(direction)[0];
							y += directions.get(direction)[1];
							x = set_Pos(x, N);
							y = set_Pos(y, N);

							if (!visited[x][y]) {
									visited[x][y] = true;
									score += 1;
							} else {
									flag = false;
									break;
							}
					}
			}
			return score;
	}

}