[백준 3190번 뱀]

728x90

오늘의 문제는  뱀이다.

 

 

 

처음엔 무조건 완전탐색!

 

시간제한과 입력의 범위를 보아하니 시간적으로는 문제가 없을 것 같았다.

구현을 어떻게 하는가가 이번 문제의 관건!

일단 사과의 자리를 표현해 줄 map [ ][ ]과 뱀의 존재유무를 따질 visited [ ][ ]를 생각했고,

뱀의 꼬리자리좌표를 ed[ ], 머리좌표를 st [ ], 뱀이 지나간 곳을 담아줄 Queue q 정도 생각했다.

또한 걸린 시간(답안)을 sec배열에 담아주었고 방향을 dr [ ], dc [ ], way(인덱스용)으로 파악해 주었다.

뱀의 방향은 idx와 시간 arr, 방향 arr 이렇게 3가지로 파악 및 갱신해 주었다.

 

글을 읽고 구현을 시작했다!

코드는 다음과 같다.

( 코드가 너무 커 보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

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

public class Main {
    public static void main(String [] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine()); // 맵의 크기
        int K = Integer.parseInt(br.readLine()); // 사과의 갯수

        int [][] map = new int [N+1][N+1]; // map 선언
        int [][] visited = new int [N+1][N+1]; // visited 선언
        Queue<int []> q = new LinkedList<>(); // 뱀자리 넣어줄 큐선언
        int [] st = {1, 1}; // 머리
        int [] ed = {1, 1}; // 꼬리
        int sec = 0; // 시간
        int [] dr = {0, 1, 0, -1}; // 4방탐색 좌표와 정보
        int [] dc = {1, 0, -1, 0};
        int way = 0;

        StringTokenizer stringT;
        for(int i = 0; i<K; i++){ // 사과를 map에 1이라 표시해주기
            stringT = new StringTokenizer(br.readLine());

            int x = Integer.parseInt(stringT.nextToken());
            int y = Integer.parseInt(stringT.nextToken());

            map[x][y] = 1;
        }

        int L = Integer.parseInt(br.readLine()); // 방향전환 L번
        int [] secArr = new int [L];
        String [] wayArr = new String [L];
        int idx = 0;
        for(int i = 0; i<L; i++){ // 각 해당 정보 담아주기
            stringT = new StringTokenizer(br.readLine());

            secArr[i] = Integer.parseInt(stringT.nextToken());
            wayArr[i] = stringT.nextToken();
        }

        visited[1][1] = 1; // 시작은 항상 좌상단이기 때문에 미리 방문처리
        while(true){ // 시작 !
            sec++; // 일단 시간 ++
            st[0] += dr[(way + 4) % 4]; // 향하고있는 방향으로 머리를 1칸 이동!
            st[1] += dc[(way + 4) % 4];
            
            // 만약 범위를 벗어나거나 이미 몸통이 존재하는곳에 머리가 닿으면 break
            if(st[0] <= 0 || st[1] <= 0 || st[0] > N || st[1] > N || visited[st[0]][st[1]] == 1){
                break;
            }
            
            // 위 조건이 아니면 방문표시하고 큐에 해당 좌표 넣어준다.
            visited[st[0]][st[1]] = 1;
            q.offer(new int [] {st[0], st[1]});
            
            // 사과가 존재하지 않는다면?
            if(map[st[0]][st[1]] == 0){
                visited[ed[0]][ed[1]] = 0; // 지금 꼬리자리 방문없애고
                int [] temp = q.poll(); // 지나온곳이 차례로 담겨있는 큐에서 하나꺼내
                ed[0] = temp[0]; // 꼬리의 좌표를 갱신해준다.
                ed[1] = temp[1];
            }

            if(idx < L && sec == secArr[idx]){ // idx가 L범위고 해당 idx의 secArr과 같다면?
                if(wayArr[idx].equals("D")){ // 좌로갈지 우로갈지 파악해주고 way에 수정!
                    way += 1;
                }else{
                    way -= 1;
                }
                idx++;
            }
        }
        
        System.out.println(sec); // 출력
    }
}

 

결과는..? Index 범위 오류가 났다 ㅎ

엥.. 왜지 눈을 씻고 찾아봐도 못 찾다가 결국 질문게시판에 들어서게 되었고,,

반례가 대부분 맞던 와중 반례를 찾아주는 사이트를 만나 이유를 알게 되었다.

 

https://testcase.ac/

Testcase AC

 

신기한 사이트 ,, 아직 베타단계지만 종종 확인할 것 같다. 광고 아님

 

아무튼, 위 코드에서의 문제는? while문 하단의 way갱신하는 부분이었다.

            if(idx < L && sec == secArr[idx]){
                if(wayArr[idx].equals("D")){
                    way = (way + 1) % 4;
                }else{
                    way = (way - 1) % 4;
                }
                idx++;
            }

처음의 코드에선 way가 계속 더해지거나 계속 빼질 수 있었다.

이런 실수를,,ㅎ

 

아무튼 매번 더할 때에도 모듈러 연산을 통해서 음수값이 나오지 않게 해 줌으로써

문제를 맞혔다!

 

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

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