[Algorithm] 백준 3190번(BOJ 3190) 뱀 문제풀이!! (java)

---

안녕하세요. Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 3190번 뱀 문제를 풀어보겠습니다.

문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다.

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

 

1. 문제 설명

문제를 읽어보셔서 아시겠지만 특별한 알고리즘보다는 주어진 내용에 맞게 구현하는 것에 초점을 두고 코드를 작성하면 어렵지 않게 풀 수 있습니다.

문제에서 주어진 조건 말고 따로 주의해야 할 점은 뱀이 방향 전환을 하고 나면 머리와 꼬리가 다른 방향을 바라보면서 매 초마다 움직이게 되고, 머리가 방향 전환을 시작한 위치에서 꼬리가 방향 전환을 할 수 있도록 구현해야 한다는 점입니다.

저는 이 부분을 List를 사용해서 머리의 방향 전환이 일어난 위치를 따로 저장해서 꼬리가 머리를 따라갈 수 있게 구현해주었습니다.

그럼 코드를 살펴보겠습니다.

 

2. Java로 문제 풀이

package study.blog.codingnojam.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

// 백준온라인저지 3190번 뱀문제 Java 문제풀이
public class BOJ_3190 {

    public static void main(String[] args) throws IOException {

        // 입력을 받기 위한 객체
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 보드판의 사이즈 받기
        int boardSize = Integer.parseInt(br.readLine());

        // 보드판을 표현할 배열 생성
        String[][] board = new String[boardSize][boardSize];

        // 보드판 배열이 String타입이므로 초기값인 null을 제거하기 위해 빈문자열로 초기화
        for (int i = 0; i < boardSize; i++) {
            Arrays.fill(board[i], "");
        }

        // 사과 개수 받기
        int appleCount = Integer.parseInt(br.readLine());

        // 사과들의 위치정보를 받아서 보드판 배열에 저장
        for (int i = 0; i < appleCount; i++) {
            String[] appleLocation = br.readLine().split(" ");
            int row = Integer.parseInt(appleLocation[0]) -1 ;
            int col = Integer.parseInt(appleLocation[1]) -1 ;
            board[row][col] = "apple";
        }

        // 방향전환 명령 개수 받기
        int commandCount = Integer.parseInt(br.readLine());

        // 방향전환 명령을 저장 할 List생성 후 List에 명령 저장
        LinkedList<String[]> commands = new LinkedList<>();
        for (int i = 0; i < commandCount; i++) {
            commands.add(br.readLine().split(" "));
        }

        // 시간을 표현할 변수
        int time = 0;

        // 보드판 배열에서의 상하좌우 움직임에 사용할 배열
        int[] moveR = {0, 1, 0, -1};
        int[] moveC = {1, 0, -1, 0};

        // 뱀의 머리 위치를 저장 할 변수
        Location head = new Location(0, 0, 0);
        
        // 뱀의 꼬리 위치를 저장 할 변수
        Location tail = new Location(0, 0, 0);
        
        // 꼬리가 방향전환을 할 시점을 저장 한 List 생성
        LinkedList<Location> tailDirections = new LinkedList<>();
        
        // 뱀의 처음 시작위치 X로 초기화 (뱀의 이동경로는 모두 X로 표기할 예정)
        board[0][0] = "X";

        // 게임 시작
        while (true) {
            // 시간 1초 증가
            time++;

            // 뱀이 사과를 먹었는지를 표현할 변수
            boolean appleEat = false;
            
            // 현재 뱀이 바라보고 있는 방향으로 1칸 이동한 위치 계산
            head.row = head.row + moveR[head.direction];
            head.column = head.column + moveC[head.direction];

            // 계산된 위치가 보드판을 벗어나거나 뱀의 몸통에 닿았는지 체크 후 해당하면 게임 종료
            if (head.row >= boardSize || head.row < 0
                    || head.column >= boardSize || head.column < 0
                    || board[head.row][head.column].equals("X")) {
                break;
            }

            // 계산된 위치에 사과가 있다면 사과를 먹은 것을 표현하기 위해 true로 값 변경
            if (board[head.row][head.column].equals("apple")) {
                appleEat = true;
            }

            // 계산된 위치로 머리 1칸 이동 
            board[head.row][head.column] = "X";

            // 방향전환 명령을 저장한 List가 비어있지 않으면
            if (commands.size() != 0) {
                // 제일 처음에 받은 명령 꺼내기
                String[] command = commands.getFirst();
                
                // 명령을 실행할 시간(초)가 현재 시간(초)와 같다면
                if (command[0].equals(String.valueOf(time))) {
                    // 명령이 시계방향 회전이라면
                    if (command[1].equals("D")) {
                        // 뱀의 머리가 바라보는 방향 시계방향으로 90도 회전
                        head.direction = head.direction + 1 == 4 ? 0 : head.direction + 1;
                    }
                    // 명령이 반시계방향 회전이라면
                    else {
                        // 뱀의 머리가 바라보는 방향 반시계방향으로 90도 회전
                        head.direction = head.direction - 1 == -1 ? 3 : head.direction - 1;
                    }
                    // 머리가 회전한 위치를 추후에 꼬리가 따라와서 그 해당 위치에서 방향전환을 해야하므로
                    // 해당 위치를 꼬리가 탐색할 방향전환 List에 추가
                    tailDirections.add(new Location(head.row, head.column, head.direction));
                    
                    // 현재 수행한 방향전환 명령을 List에서 제거
                    commands.removeFirst();
                }
            }

            // 뱀이 사과를 먹었으면 꼬리는 가만히 있어야하므로, 사과를 먹지 않았을 때만 로직수행
            if (!appleEat) {
                
                // 현재 보드판에서 꼬리가 위치한 곳 빈문자열로 값 변경
                board[tail.row][tail.column] = "";
                
                // 꼬리가 바라보는 방향으로 꼬리를 1칸 이동
                tail.row = tail.row + moveR[tail.direction];
                tail.column = tail.column + moveC[tail.direction];

                // 머리가 방향전환을 한적이 있다면
                if (tailDirections.size() != 0) {
                    // 시간순서대로 List에 저장되므로 List에서 제일 앞의 값 가져오기
                    Location temp = tailDirections.getFirst();
                    
                    // 머리가 방향전환을 한 위치가 현재 꼬리가 이동한 위치와 같다면
                    if (tail.row == temp.row && tail.column == temp.column) {
                        // 꼬리도 머리와 같은 방향으로 방향회전
                        tail.direction = temp.direction;
                        // 방향전환을 했으므로 List에서 해당 명령 제거
                        tailDirections.removeFirst();
                    }
                }
            }
        }

        // 게임이 종료되었을 때의 시간(초) 출력
        System.out.println(time);
    }

    // 머리와 꼬리의 위치를 표현할 클래스
    static class Location {
        // 행
        int row;
        // 열
        int column;
        // 현재 바라보는 방향
        int direction;

        public Location(int row, int column, int direction) {
            this.row = row;
            this.column = column;
            this.direction = direction;
        }
    }
}

 

작성한 코드의 라인마다 주석을 달아놓았습니다.

주석과 코드를 같이 살펴보시면 이해하는데 크게 어렵지 않으실 겁니다.

이해가 되지 않거나 궁금하신 점이 있다면 댓글로 남겨주시면 답변드리겠습니다.

감사합니다.

---