백준 3190 뱀

정처기 공부를 한다고 오랜만에 문제를 풀었다.

사실 정처기 하다가 지겨워서 잠깐 풀다가 다음날 또 풀다가, 다시 풀었다. 

 

처음에 뱀을 저장하는 방식으로 vector를 사용했다가 코드가 너무 복잡해져서 다른 방법을 생각해보니 deque가 생각났다.

뱀이 이동할 때 추가되거나 삭제 되는 곳은 머리 혹은 꼬리 뿐이기 때문에 쉽게 front, back을 수정을 할 수 있는 deque을 사용하여 다시 코드를 작성했다.

 

먼저, 벽을 만나거나 몸을 만나면 종료를 해야 하기 때문에 이를 처리한다.

그리고 다음 칸이 사과면 꼬리는 그대로 두고, 머리만 front에 추가한다.

다음 칸이 사과가 아니라면 머리를 front에 추가하고, 꼬리는 back에서 pop시킨다.

 

방향만 잘 설정해주고, 방향을 바꾸는 시간대를 따로 vector로 저장해서 관리만 해주면 쉽게 풀리는 문제이다.

한 가지 실수를 한 부분이 있다면, 사과를 먹고 나서 해당 위치를 false로 처리해줘야 하는데, 이를 해주지 않아서 왜 틀렸다고 하는지 몰랐다. 꼼꼼히 풀어야 겠다.

그리고 지금 다시보니 굳이 구조체를 사용할 필요가 없이 pair로 처리했어도 될 것 같다. 나중에 코드를 한 번 수정해야 겠다.

 

코드는 아래와 같다.

#include <iostream>
#include <deque>
#include <queue>
using namespace std;
 
int n, k, l;
 
bool map[102][102];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
//뱀을 나타내기 위한 structure
typedef struct snake {
    int row;
    int col;
};
 
//몸이랑 부딪히는지 체크한다.
bool check(deque<snake> s, int nr, int nc) {
    int row, col;
    for (int i = 1; i < s.size(); i++) {
        row = s[i].row;
        col = s[i].col;
        if (nr == row && nc == col)return true;
    }
    return false;
}
 
int main() {
    cin >> n >> k;
    //방향을 변겨할 시간
    int next_sec;
    //사과 위치 표시
    for (int i = 0; i < k; i++) {
        int row, col;
        cin >> row >> col;
        map[row - 1][col - 1] = true;
    }
    cin >> l;
    //방향 변경하는 경우를 입력 받는다. 해당 시간을 처리하면 지워야 하므로 queue로 처리한다.
    queue<pair<int, int>> q;
    for (int i = 0; i < l; i++) {
        int time;
        char dir;
        cin >> time >> dir;
        //처음꺼는 따로 저장한다.
        if (i == 0)next_sec = time;
        //왼쪽은 0, 오른쪽은 1
        if (dir == 'L')q.push(make_pair(time, 0));
        else q.push(make_pair(time, 1));
    }
    //뱀
    deque<snake> s;
    struct snake temp;
    temp.row = 0;
    temp.col = 0;
    //처음 머리를 넣는다.
    s.push_front(temp);
 
    //시간을 측정하기 위한 변수
    int sec = 0;
    //처음에는 오른쪽이니까 1번
    int dir = 1;
 
    while (1) {
        //dir을 확인하여 다음 칸을 본다.
        int nr, nc;
        nr = s.front().row + dr[dir];
        nc = s.front().col + dc[dir];
        //sec 증가.
        sec++;
        //벽인 경우 종료
        if (nr < 0 || nr >= n || nc < 0 || nc >= n)break;
        //몸인 경우 종료
        if (check(s, nr, nc))break;
        //다음칸으로 갈 수 있는 경우에는 다음칸을 머리에 추가한다.
        temp.row = nr;
        temp.col = nc;
        s.push_front(temp);
        //사과가 있는 경우 꼬리를 그대로 둔다. 사과가 없는 경우 꼬리를 자른다.
        if (!map[nr][nc]) s.pop_back();
        else map[nr][nc] = false;
        //1초가 경과했으니 입력받은 시간과 같으면 방향을 바꾼다.
        if (!q.empty()) {//방향이 변경되는 경우가 없다면 그냥 통과
            if (sec == next_sec) {//다음에 변경될 시간이 되었다면 방향을 바꾼다.
                int nd = q.front().second;
                q.pop();
                //왼쪽으로 갈 때
                if (nd == 0) {
                    dir = (dir + 3) % 4;
                }
                else {//오른쪽으로 갈 때
                    dir = (dir + 1) % 4;
                }
                //만약 다음에 또 방향을 변경해야 하는 시간이 있다면 갱신, 다음에 dir을 갱신해야 하므로 pop은 시키지 않는다.
                if (!q.empty())next_sec = q.front().first;
            }
        }
        /*출력(디버깅
        for (int i = 0; i < s.size(); i++) {
            cout << '(' << s[i].row << ',' << s[i].col << ')' << ' ';
        }
        cout << endl;
        */
    }
 
    cout << sec << endl;
 
    return 0;
}

============================================================================

2019.08.15

4개월 만에 Java로 다시 풀게 되었다. 한 번 풀었던 문제인데도 중간에 엉켰던 부분이 있어서 1시간 좀 넘게 걸려서 풀었다.

deque로 풀어야 된다는 것을 좀 늦게 떠올렸고, 방향 전환 시간을 queue에서 꺼낼 때 empty 처리를 해주지 않아서 계속 해맸다. 

row와 col을 class로 만들지 않고 처리하려 했더니, 사과를 먹은 경우 꼬리는 빼지 않아야 하는데, row, col 두 개를 넣다보니 queue에서 꺼내지 않으면 col을 확인할 수가 없었다.

그래서 row는 꺼내서 확인하고, col은 peek으로 확인한 후 다시 row를 집어 넣어야 했다. 처음에 이를 찾지 못해서 디버깅 해야 했고, 코드도 복잡해 졌다. 따라서 동시에 2가지 값을 확인해야 하고 또 무조건 꺼내는 것이 아니라 조건에 따라 꺼내지 않고 확인만 해야 할 때는 그냥 class로 만드는 것이 더 편하다는 것을 알았다.

저번 보다 나은 점은 뱀이 현재 위치하고 있는 위치를 boolean 배열로 선언해서 처리한 것이다. 덕분에 코드를 쉽고 짧게 짤 수 있었다.

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int row, col, dir;
 
        int n = Integer.parseInt(br.readLine());
        int[][] map = new int[n][n];
        boolean[][] s = new boolean[n][n];
 
        int apples = Integer.parseInt(br.readLine());
        for (int i = 0; i < apples; i++) {
            st = new StringTokenizer(br.readLine());
            row = Integer.parseInt(st.nextToken());
            col = Integer.parseInt(st.nextToken());
            map[row - 1][col - 1] = 1;
        }
 
        int cnt = Integer.parseInt(br.readLine());
        Queue<Integer> nt = new LinkedList<Integer>();
        Queue<String> nd = new LinkedList<String>();
 
        for (int i = 0; i < cnt; i++) {
            st = new StringTokenizer(br.readLine());
            nt.offer(Integer.parseInt(st.nextToken()));
            nd.offer(st.nextToken());
        }
 
        Deque<Integer> snake = new LinkedList<Integer>();
        snake.addFirst(0);
        snake.addFirst(0);
        snake.addFirst(1);
 
        s[0][0] = true;
 
        int now_time = 0;
        while (true) {
            int next_time = nt.poll();
            String next_dir = nd.poll();
 
            dir = snake.pollFirst();
            while (true) {
                now_time++;
                row = snake.pollFirst();
                col = snake.peekFirst();
                snake.addFirst(row);
 
                int nr = row + dr[dir];
                int nc = col + dc[dir];
 
                if (nr < 0 || nr >= n || nc < 0 || nc >= n || s[nr][nc]) {
                    System.out.println(now_time);
                    return;
                }
 
                // 머리 추가
                s[nr][nc] = true;
                snake.addFirst(nc);
                snake.addFirst(nr);
                // 사과가 아니면 꼬리를 삭제
                if (map[nr][nc] != 1) {
                    int tcol = snake.pollLast();
                    int trow = snake.pollLast();
                    s[trow][tcol] = false;
                } else {// 사과면 사과 먹은 표시
                    map[nr][nc] = 0;
                }
 
                if (now_time == next_time) {
                    switch (next_dir) {
                    case "L":
                        dir = (dir + 3) % 4;
                        break;
                    case "D":
                        dir = (dir + 1) % 4;
                        break;
                    }
                    if(!nt.isEmpty())
                        next_time = nt.poll();
                    if(!nd.isEmpty())
                        next_dir = nd.poll();
                }
 
            }
        }
    }
}