1.1.1 구조적,집합적,선언적 질의 언어

• 원하는 결과집합을 만드는 과정은 절차적
• 즉, 프로시저가 필요함
• 프로시저를 만들어내는 DBMS 내부 엔진이 SQL 옵티마이저
• 'SQL 최적화' 란 DBMS 내부에서 프로시저를 작성하고 컴파일해서 실행 가능한 상태로 만드는 전 과정을 의미

1.1.2 SQL 최적화

① SQL파싱 사용자로부터 SQL을 전달받으면 가장 먼저 SQL 파서가 파싱을 진행

• 파싱 트리 생성
• Syntax 체크: 문법적 오류가 없는지 확인
• Semantic 체크: 의미상 오류가 없는지 확인

② SQL최적화 옵티마이저가 SQL 최적화를 맡는다. (가장 효율적인 실행경로 선택)

③ 로우 소스 생성 SQL 옵티마이저가 선택한 실행경로를 실행 가능한 코드 또는 프로시저 형태로 포맷팅하는 단계

1.1.3 SQL 옵티마이저

SQL 옵티마이저 : 사용자가 원하는 작업을 가장 효율적으로 수행할 수 있는 최적의 데이터 엑세스 경로를 선택해주는 DBMS의 핵심 엔진

최적화 단계는 다음과 같다.

1. 사용자로부터 전달받은 쿼리를 수행하는 데 후보군이 될만한 실행계획들을 찾아낸다.
2. 데이터 딕셔너리에 미리 수집해 둔 오브젝트 통계 및 시스템 통계정보를 이용해 각 실행계획의 예상비용 산정한다.
3. 최저 비용을 나타내는 실행계획을 선택한다.

1.1.4 실행계획과 비용

책에서 SQL 옵티마이저를 자동차 네비게이션과 유사하다고 표현한다. 네비게이션이 제공하는 도착 예상시간이 예상시간이듯, SQL 실행계획에 표시되는 Cost도 예상치이다. (여러 통계정보를 활용하여 계산해낸 값)

1.1.5 옵티마이저 힌트

네비게이션이 항상 최적의 경로를 선택을 하듯, SQL 옵티마이저도 대부분 좋은 선택을 하지만 완벽하지 않다.

개발자가 '옵티마이저 힌트'를 통해 데이터 액세스 경로를 바꿀 수 있다.

자주사용하는 힌트 목록들이 책에 소개되어 있다.

1.2 SQL 공유 및 재사용

1.2.1 소프트 파싱 vs. 하드 파싱

라이브러리 캐시

• 내부 프로시저를 반복 재사용할 수 있도록 캐싱해 두는 메모리 공간
• 라이브러리 캐시는 SGA 구성요소다.

사용자가 SQL 문 전달 > DBMS는 SQL 파싱 후, 해당 SQL이 라이브러리 캐시에 존재하는지 확인 > 캐시에 존재 ? 곧바로 실행 단계 : 최적화 단계

SQL을 캐시에서 찾아 곧바로 실행 단계로 넘어가는 것을 소프트 파싱, 찾이 못해 최적화 및 로우 소스 생성까지 모두 거치는 것을 하드 파싱

SQL최적화 과정은 하드하다. (최적화 과정에 엄청난 연산이 필요하기 때문) 이러한 최적화 과정을 거쳐 생성된 내부 프로시저를 한 번 사용하고 버리면 ? 아깝다. 이것이 라이브러리 캐시가 필요한 이유이다.

1.2.2 바인드 변수의 중요성

바인드 변수를 잘 사용하면 하드파싱을 최초 한번만 하고, 캐싱된 SQL을 수없이 재사용할 수 있다.

1.3 데이터 저장 구조 및 I/O 메커니즘

1.3.1 SQL이 느린 이유

십중팔구 I/O 때문 (디스크 I/O) 프로세스가 디스크에서 데이터를 읽어야하면 waiting 상태에서 I/O가 완료되기를 기다린다. 이 때, 여러 프로세스가에 의해 동시에 I/O Call 발생하면 대기시간도 늘어난다. (디스크에서 데이터를 읽어와야 하는데 오래 걸린다)

1.3.2 데이터베이스 저장 구조

데이터를 저장하려면 먼저 테이블스페이스를 생성해야 한다. 테이블스페이스는 세그먼트를 담는 컨테이너로써, 여러개의 데이터파일로 구성된다. 세그먼트는 테이블, 인덱스처럼 저장공간이 필요한 오브젝트이다. 세그먼트는 여러개의 익스텐트로 구성된다. ? 아직 이해가 잘 안됐다.

사용자가 입력한 레코드를 실제로 저장하는 공간은 데이터 블록이다.

1.3.3 블록 단위 I/O

블록이 DBMS가 데이터를 읽고 쓰는 단위이다.

• 특정 레코드 하나를 읽고 싶어도, 컬럼 하나만 읽고 싶어도 블록을 통째로 읽는다.
• 오라클은 기본적으로 8KB 크기의 블록을 사용한다.
• 인덱스도 블록 단위로 데이터를 읽고 쓴다.

1.3.4 시퀀셜 엑세스 vs. 랜덤 엑세스

테이블이나 인덱스 블록을 엑세스하는 방식 : 시퀀셜 엑세스, 랜덤 엑세스

아직 뒤에는 이해가 안된듯.. 그냥 책내용 고대로 적게된다.. 추후에 완성하기 ..

• 책) 친절한 SQL 튜닝 정리

생각 정리

각 단계별로 함수를 만들었다.

1. rotate() - 벨트와 로봇이 함께 한 칸 회전하는 함수

• 로봇이 내리는 칸에 이르렀다면 내리기

2. robotsMove() 가장먼저 벨트에 올라간 로봇부터(=내리는 위치, N-1에서부터) if (이동하고자 하는 칸에 로봇이 없고 && 내구도가 1 이상)이라면 로봇을 이동한다.

• 이동된 자리에 로봇이 생기고, 원래 있던 자리에는 로봇 없애주기
• 로봇 이동시키고 해당 자리의 내구도 감소시켜주기
• 로봇이 내리는 칸에 이르렀다면 내리기

3. enterNewRobot() 올리는 칸의 내구도가 0이 아니면(= 1 이상이면) 로봇 올림 (로봇 올리고 올리는 칸의 내구도 감소시켜주기)

4. boolean isExit() 내구도가 0인 칸의 개수가 K개 이상이라면 true, 그렇지 않다면 false를 리턴시켜주기

코드

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

public class Main {
    static int N, K;
    static int[] arr;
    static int[] robot; //0: 로봇 존재 x, 1: 로봇 존재
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[2*N];
        robot = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<2*N; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        int stage = 1;
        while(true) {
            //1단계 회전하기
            rotate();
            //2단계 맨 앞의 로봇부터 (N-1에 가까울수록 먼저들어간 것임) 벨트가 이동한 방향으로 이동할 수 있으면 이동
            robotsMove();

            enterNewRobot();

            if(isExit()) break;
            else stage++;
        }

        System.out.println(stage);

    }

    static void rotate() { //컨베이어벨트 위의 로봇도 회전시켜주어야 함 
        int start = arr[2*N-1];
        for(int i=2*N-2; i>=0; i--) {
            arr[i+1] = arr[i];
        }
        arr[0] = start;

        for(int i=N-2; i>=0; i--) {
            robot[i+1] = robot[i];
            if(i+1 == N-1) //로봇이 내리는 위치에 도달하면 그 즉시 내림
                robot[i+1] = 0; //로봇이 내렸으니 0으로 바꿔준다 
        }
        robot[0] = 0;

    }

    static void robotsMove() {
        int n = N-2;
        while(n > 0) {
            if(robot[n] == 1 && robot[n+1] == 0 && arr[n+1] >= 1) { //앞에서부터 로봇이 있을 때, 이동하고자 하는 칸에 로봇 없음 && 내구도가 1 이상임
                robot[n+1] = 1; //로봇을 옮김 
                if(n+1 == N-1) //로봇이 내리는 위치에 도달하면 그 즉시 내림
                    robot[n+1] = 0; //로봇이 내렸으니 0으로 바꿔준다 
                robot[n] = 0; //로봇이 ㅇㅣ동했으니 원래 있던 곳에는 없어짐
                arr[n+1]--; //내구도 1감소
            }
            n--;
        }
    }

    static void enterNewRobot() {
        if(arr[0] >= 1){ //올리는 위치에 있는 칸의 내구도가 0이 아니면
            robot[0] = 1; //올리는 위치에 로봇을 올린다.
            arr[0]--; //로봇을 올리는 위치에 올리거나 ..~ 하면 그 칸의 내구도는 즉시 1만큼 감소한다.
        }
    }

    static boolean isExit() {
        int cnt = 0;
        for(int a: arr)
            if(a == 0) cnt++; //내구도가 0이라면 증가 

        if(cnt >= K) return true; //내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다.
        else return false; //그렇지 않다면 1번으로 돌아간다.
    }
}

생각정리

• 인구이동이 가능할 때 (canMove변수를 설정해서 true일때 while문이 작동하도록 하였다.)

  • canMove false처리
  • 방문하지 않았을 때 bfs를 호출한다.
  • 해당 반복문이 끝나면 방문여부를 초기화해준다.

  • bfs내에서

    • 상하좌우를 탐색하면서 (국경선이 맞닿아 있는 국가) 두 나라의 인구차이가 L이상 R이하라면
      • queue에 해당 위치를 넣는다.
      • 방문표시를 한다.
      • 해당 위치를 리스트에 저장한다. (연합을 이루고 있는 국가의 인구수를 추후에 업데이트하기 위해)
      • '합의 인구수' 와 '연합을 이루고 있는 칸의 개수'를 각각 업데이트한다.
    • bfs 내에서 while문이 끝나고 연합을 이루는(=리스트에 저장된) 국가의 인구수 업데이트한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, L, R;
    static int[][] arr;
    static boolean[][] visited;
    static boolean canMove = true;
    static class Position{
        int x, y;
        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        arr = new int[N][N];
        visited = new boolean[N][N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int days = 0;
        while(canMove) {
            canMove = false;
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(!visited[i][j])
                        bfs(i, j);
                }
            }

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    visited[i][j] = false;
                }
            }
            if(canMove) days++;
        }

        System.out.println(days);

    }

    static void bfs(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        int howMany = 0;
        int cnt = 0;
        List<Position> list = new LinkedList<>();

        queue.add(new Position(x, y));
        visited[x][y] = true;
        list.add(new Position(x, y));
        howMany += arr[x][y];
        cnt++;

        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny <0 || nx >= N || ny >= N) continue;
                if(visited[nx][ny]) continue;
                if(Math.abs(arr[out.x][out.y] - arr[nx][ny]) < L || Math.abs(arr[out.x][out.y] - arr[nx][ny]) > R) continue;
                list.add(new Position(nx, ny));
                queue.add(new Position(nx, ny));
                visited[nx][ny] = true;

                howMany += arr[nx][ny];
                cnt++;

            }
        }


        if(list.size() > 1) {
            canMove = true;
            for(Position l : list)
                arr[l.x][l.y] = (int) Math.floor(howMany / cnt);
        }
    }
}

1. cctv들의 개수만큼, 각 cctv들의 (1~5번) 가능한 위치를 dfs를 통해 구한다.
2. cctv (위치, cctv번호) 와 그 때의 방향을 파라미터로 하는 함수를 통해 그 때의 사각지대 개수를 구한다.
3. 최소 사각지대 개수를 업데이트 한다.

생각하지 못한 것

dfs를 통해 가능한 위치를 구할 때, 그냥 방향만 구하면 되는데 cctv의 배열과 방향을 2차반복문을 통해 구하다가 틀렸다.

코드

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

public class Main {

    static class CCTV {
        int x, y;
        int num;
        CCTV(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }
    static int N, M, min = Integer.MAX_VALUE;
    static int[][] company, new_company;
    static List<CCTV> cctv = new LinkedList<>();
    static int C;
    static int[] cc ;
    static boolean[][][] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        company = new int[N][M];
        new_company = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                company[i][j] = Integer.parseInt(st.nextToken());
                new_company[i][j] =  company[i][j];
                if(company[i][j] >= 1 && company[i][j]<=5) {
                    cctv.add(new CCTV(i, j, company[i][j]));
                }
            }
        }

        C = cctv.size();
        cc = new int[C]; //cctv의 dir

        dfs(0);
        System.out.println(min);
    }

    static void dfs(int curr) {
        if(curr == C) {
            for(int i=0; i<C; i++){ 
                getSpaceSize(cctv.get(i), cc[i]); 
            }
            //cctv의 방향에 따라 사각지대 구하고 사무실 상태 원래대로

            int cnt = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(new_company[i][j] == 0)
                        cnt++;
                    new_company[i][j] =  company[i][j];
                }
            }


            min = Math.min(min, cnt);

            return ;
        }

            for(int j=0; j<4; j++) {
               // if(!visited[cctv.get(i).x][cctv.get(i).y][j]) {

                    //System.out.println("("+cctv.get(i).x+","+cctv.get(i).y+") => " + company[cctv.get(i).x][cctv.get(i).y]);
                   // visited[cctv.get(i).x][cctv.get(i).y][j] = true;
                    cc[curr] = j;
                    dfs(curr+1);
                   // visited[cctv.get(i).x][cctv.get(i).y][j] = false;
              //  }
            }
       // }
    }

    static void getSpaceSize(CCTV c, int dir) {
        int num = c.num;
        int x = c.x;
        int y = c.y;
       // int dir = dir;

        if(num == 1) {
            if(dir == 0) { //x, y ~ x, M-1까지
                for(int i = y+1; i<M; i++){
                    if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                        break; //이전에 -1로 바꾼거 돌려놓아야 함..
                    new_company[x][i] = -1; // 감시
                }
            }
            if(dir == 1) { //x, y ~ N-1, y까지
                for(int i = x+1; i<N; i++){
                    if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[i][y] = -1; // 감시
                }
            }
            if(dir == 2) { //x,0 ~ x, y 까지
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[x][i] = -1; // 감시
                }
            }
            if(dir == 3) { //0,y ~ x,y 까지
                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[i][y] = -1; // 감시
                }
            }
        }

        else if(num == 2) {
            boolean flag = true;
            if(dir == 0 || dir == 2) { //x, 0 ~ x, M-1 까지
                // for(int i = 0; i<M; i++){
                //     if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                //         break;
                //     new_company[x][i] = -1; // 감시
                // }
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) {//벽이면 더 이상 감시 불가능
                        //flag = false;
                        break;
                    }
                    new_company[x][i] = -1; // 감시
                }
        //        if(flag){
                    for(int i = y+1; i<M; i++){
                        if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                            break; //이전에 -1로 바꾼거 돌려놓아야 함..
                        new_company[x][i] = -1; // 감시
                    }
         //       }


            }
            if(dir == 1 || dir == 3) { //0, y ~ N-1, y까지

                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6){ //벽이면 더 이상 감시 불가능
                      //  flag = false;
                        break;
                    }
                    new_company[i][y] = -1; // 감시
                }
        //        if(flag){
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[i][y] = -1; // 감시
                    }
          //      }

            }
        }

        else if(num == 3) {

            boolean flag = true;
            if(dir == 0) { //0,y ~ x, y / x,y ~ x,M-1까지  

                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[i][y] = -1; // 감시
                }
            //    if(flag) {
                    for(int i = y+1; i<M; i++){
                        if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[x][i] = -1; // 감시
                    }
           //     }

            }
            if(dir == 1) { //x,y ~ x, M-1 / x,y ~ N-1, y
                for(int i = y+1; i<M; i++){
                    if(new_company[x][i] == 6){ //벽이면 더 이상 감시 불가능
                        flag = false;
                        break;
                    }
                    new_company[x][i] = -1; // 감시
                }
           //     if(flag) {
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[i][y] = -1; // 감시
                    }
          //      }

            }
            if(dir == 2) { //x,0 ~ x, y 까지
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[x][i] = -1; // 감시
                }
               // if(flag) {
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[i][y] = -1; // 감시
                    }
             //   }

            }
            if(dir == 3) { //0,y ~ x,y 까지
                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[i][y] = -1; // 감시
                }
              //  if(flag){
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                        break;
                    new_company[x][i] = -1; // 감시
                }
              //  }

            }
        }

        else if(num == 4) {
            boolean flag = true;

            if(dir == 0) { // x,0 ~ x, M-1 / 0,y ~x,y
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) {//벽이면 더 이상 감시 불가능
                        flag = false;
                        break;
                    }
                    new_company[x][i] = -1; // 감시
                }
              //  if(flag){
                    for(int i = y+1; i<M; i++){
                        if(new_company[x][i] == 6){ //벽이면 더 이상 감시 불가능
                            flag = false;
                            break; //이전에 -1로 바꾼거 돌려놓아야 함..
                        }
                        new_company[x][i] = -1; // 감시
                    }
               // }
               // if(flag) {
                    for(int i = x-1; i>=0; i--){
                        if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[i][y] = -1; // 감시
                    }
               // }
            }

            if(dir == 1) { //0,y ~ x, y / rmc ~ r, M-1
                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6){ //벽이면 더 이상 감시 불가능
                        flag = false;
                        break;
                    }
                    new_company[i][y] = -1; // 감시
                }
               // if(flag){
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) { //벽이면 더 이상 감시 불가능
                            flag = false;
                            break;
                        }
                        new_company[i][y] = -1; // 감시
                    }
              //  }
               // if(flag) {
                    for(int i = y+1; i<M; i++){
                        if(new_company[x][i] == 6){ //벽이면 더 이상 감시 불가능
                            flag = false;
                            break;
                        }
                        new_company[x][i] = -1; // 감시
                    }
                //}
            }
            if(dir == 2) { //x,0 ~ x, M-1 / x,y ~N-1,y
                for(int i = y-1; i>=0; i--){
                    if(new_company[x][i] == 6) {//벽이면 더 이상 감시 불가능
                        flag = false;
                        break;
                    }
                    new_company[x][i] = -1; // 감시
                }
              //  if(flag){
                    for(int i = y+1; i<M; i++){
                        if(new_company[x][i] == 6){ //벽이면 더 이상 감시 불가능
                            flag = false;
                            break; //이전에 -1로 바꾼거 돌려놓아야 함..
                        }
                        new_company[x][i] = -1; // 감시
                    }
             //   }
               // if(flag) {
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[i][y] = -1; // 감시
                    }
             //   }
            }
            if(dir == 3) { //0,y ~ N-1, y / x,0 ~ x, y
                for(int i = x-1; i>=0; i--){
                    if(new_company[i][y] == 6){ //벽이면 더 이상 감시 불가능
                        flag = false;
                        break;
                    }
                    new_company[i][y] = -1; // 감시
                }
               // if(flag){
                    for(int i = x+1; i<N; i++){
                        if(new_company[i][y] == 6) { //벽이면 더 이상 감시 불가능
                            flag = false;
                            break;
                        }
                        new_company[i][y] = -1; // 감시
                    }
               // }
                //if(flag){
                    for(int i = y-1; i>=0; i--){
                        if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                            break;
                        new_company[x][i] = -1; // 감시
                    }
               // }
            }
        }

        else if(num == 5) {

            for(int i = y+1; i<M; i++){
                if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                    break; //이전에 -1로 바꾼거 돌려놓아야 함..
                new_company[x][i] = -1; // 감시
            }

            for(int i = x+1; i<N; i++){
                if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                    break;
                new_company[i][y] = -1; // 감시
            }

            for(int i = y-1; i>=0; i--){
                if(new_company[x][i] == 6) //벽이면 더 이상 감시 불가능
                    break;
                new_company[x][i] = -1; // 감시
            }


            for(int i = x-1; i>=0; i--){
                if(new_company[i][y] == 6) //벽이면 더 이상 감시 불가능
                    break;
                new_company[i][y] = -1; // 감시
            }



        }

        else return ;
    }
}

1. 같은 색 뿌요가 4개이상 상하좌우로 연결되면 같은색 뿌요 한번에 없어진다.
   • 1.1) 4개이상 상하좌우로 연결되어 있는지 확인하기
     • 1.2) 해당 뿌요들은 없애기 (빈칸처리하기 .)
     2. 뿌요들이 없어지면 위에 있던 뿌요들이 떨어진다.
     • 2.1 밑에서부터 그 다음칸이 빈칸이면 위치를 바꿈 (빈칸을 뿌요 위로 올림)

• 1,2 가 끝나면 뿌요에 대해 방문처리 초기화하기
• 이 모든 과정은 뿌요를 더이상 없앨 수 없을 때까지 반복

참고링크

생각하지 못한 것

1. 밑에 있던 뿌요들이 없어지면 그 자리를 위에 있던 뿌요들이 채우는 것을 어떻게 구현해야할지 감이 잡히지 않았다.

• 밑에서부터 그 다음 밑의 칸이 빈칸일 경우 둘의 위치를 바꾸어 주었다.

2. '터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.' 라는 룰이 있다. 한번에 다 터뜨린 후, 연쇄의 개수를 증가시켜주어야 한다. => bfs함수 내에서 실행하면, 터뜨려질 때마다 증가되어서 안된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    static char[][] puyo = new char[12][6];
    static boolean isPuyo = true;
    static boolean[][] visited = new boolean[12][6];
    static class Position{
        int x, y;
        Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int cnt = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0; i<12; i++) {
            String str = br.readLine();
            for(int j=0; j<6; j++) {
                puyo[i][j] = str.charAt(j);
            }
        }
        while(isPuyo) {
            isPuyo = false;

            recycle();

            for(int i=0; i<12; i++) {
                for(int j=0; j<6; j++) {
                    if(puyo[i][j] != '.' && !visited[i][j]) {
                        bfs(i, j);
                    }
                }
            }

            if(isPuyo) cnt++;

            resetVisited();

        }
        System.out.println(cnt);

    }

    static void bfs(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        List<Position> list = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        //System.out.println(x + " , " + y);
        queue.add(new Position(x, y));
        list.add(new Position(x, y));
        visited[x][y] = true;
        char color = puyo[x][y];
        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx<0 || ny < 0 || nx >= 12 || ny >= 6) continue;
                if(visited[nx][ny] || color != puyo[nx][ny] || puyo[nx][ny] == '.') continue;

                queue.add(new Position(nx, ny));
                list.add(new Position(nx, ny));
                visited[nx][ny] = true;
            }
        }

        if(list.size() >= 4) {
            isPuyo = true;

            for(Position l : list){
                puyo[l.x][l.y] = '.';
            }
            //cnt++;
        }
    }

    static void recycle() {
        for(int i=0; i<6; i++) {
            for(int j=10; j>=0; j--) {
                int tmp = j;
                while(tmp < 11 && puyo[tmp+1][i] == '.') {
                    char ch = puyo[tmp][i];
                    puyo[tmp][i] = puyo[tmp+1][i];
                    puyo[tmp+1][i] = ch;
                    tmp++;
                }
            }
        }
    }

    static void resetVisited() {
        for(int i=0; i<12; i++) {
            for(int j=0; j<6; j++) {
                visited[i][j] = false;
            }
        }
    }

}

D[n] = 수열의 n번째 요소까지 가장 긴 증가하는 부분 수열의 길이 S[n] = 주어진 수열의 n번째 요소

단순하게 D[n]이 업데이트될 때의 수열의 n번째 요소들을 따로 저장하면 될 것이라고 생각했다. 골드인데 금방 풀수있을거 같아 !!!! 라고할뻔

생각하지 못한 것

D[n]이 업데이트될 때는 S[1]~S[n-1] 까지의 숫자들과 S[n]를 비교해서 S[n]보다 S[i]가 작을 때 D[n]을 업데이트한다. 그러니, 같은 S[n]이 여러번 나올 수 있다는 것이다.

검색을 해보았고,

가장 긴 증가하는 부분 수열을 출력할 때는 D[n]의 최장길이, S배열, D배열을 가지고 추적하며 구해갔다.

❓ 왜 D[1]이 아닌 D[n]부터 구하는 것일까?

• D[i-1]과 D[i]의 값이 같다면 거꾸로 탐색했을 때 S[i]이 S[i-1]보다 더 작은 수이기 때문이다.
• S[i-1] < S[i]이었다면 D[i-1]과 D[i]의 값이 같지 않았을 것이다.
• 즉, D[i]의 값과 D[j]의 값이 같다면 i < j일 때 S[i] > S[j]가 된다고 이해했다.

for(int i=n; i>0; i--)
    if(D[i] == max) {
        //이때의 S[i]가 수열의 max번째 수이다.
        max --;
    }

n부터 구하기 때문에 오름차순이 아닌 내림차순의 형태로 수열의 값을 구하게되고, 오름차순으로 나타내기 위해 stack을 사용한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

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[] S = new int[n+1];
        int[] D = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++)
            S[i] = Integer.parseInt(st.nextToken());

        D[1] = 1;
        int max = 1;
        for(int i=2; i<=n; i++) {
            D[i] = 1;
            for(int j=1; j<i; j++) {
                if(S[j] < S[i] && D[i] < D[j] + 1)
                    D[i] = D[j] + 1;
            }
            max = Math.max(max, D[i]);
        }


        System.out.println(max);

        Stack<Integer> stack = new Stack<>();

        // D[i]의 값이 같다면 거꾸로 탐색했을 때 먼저 나오는 값이 더 작은 수
        // 왜냐하면 값이 더 컸다면, D[i]의 값이 작지 않았을 것이다.

        for(int j=n; j>0; j--){
            if(D[j] == max){
                stack.push(S[j]);
                max--;
            }
        }

       while(!stack.isEmpty())
            System.out.print(stack.pop() + " ");
    }
}

계단 오르기처럼 풀면된다고 생각해서 자신감을 얻음..

생각하지 못한 것

연속해서 포도주를 마시지 않아도 된다. 즉, k번째 포도주 앞에 있을 때, k번째 포도주를 마시지 않는 것이 최댓값이 될 수가 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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[] S = new int[n+1];
        int[][] D = new int[3][n+1];
        for(int i=1; i<=n; i++) {
            S[i] = Integer.parseInt(br.readLine());
        }

       // D[0][1] = 0;
        D[1][1] = S[1];
        D[2][1] = S[1];


        int max = Math.max(D[0][1], Math.max(D[1][1], D[2][1]));
        for(int i=2; i<=n; i++) {
            D[0][i] = Math.max(D[0][i-1], Math.max(D[1][i-1], D[2][i-1])); 
            D[1][i] = Math.max(D[0][i-2], Math.max(D[2][i-2] ,D[1][i-2])) + S[i]; 
            D[2][i] = Math.max(D[0][i-1], D[1][i-1]) + S[i]; 
        }

        System.out.println(max);
    }
}

D[N] = 2 X N개의 스티커 중 두변을 공유하지 않는 스티커 정수의 최댓값 D[3]을 생각하는 과정에서 막혔다.

생각하지 못한 것

2 X N개의 스티커에 대해서 D[0][N], D[1][N] 두가지로 나누어 생각하기

• D[0][N] = 2 X N개의 스티커 중 _오른쪽 상단_을 선택했을 때 두변을 공유하지 않는 스티커 정수의 최댓값
• D[1][N] = 2 X N개의 스티커 중 _오른쪽 하단_을 선택했을 때 두변을 공유하지 않는 스티커 정수의 최댓값

D[N] = D[0][N]과 D[1][N] 중 큰 값

그렇다면, D[0][N]과 D[1][N]은 어떻게 구할까 ? N이 3일때의 경우를 나타내 보았다.

코드

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

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

        for(int i=0; i<T; i++) {
            int n = Integer.parseInt(br.readLine());
            int[][] arr = new int[2][n];
            int[][] D = new int[2][n];

            for(int j=0; j<2; j++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for(int k=0; k<n; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            //arr[0][j] j번째 스티커의 위쪽 숫자, arr[1][j] j번째 스티커의 아래쪽 숫자 
            for(int j= 0; j<n; j++) {
                if(j == 0){
                    D[0][0] = arr[0][0];
                    D[1][0] = arr[1][0];
                }
                else if(j == 1) {
                    D[0][1] = D[1][0] + arr[0][1];
                    D[1][1] = D[0][0] + arr[1][1];
                }
                else {
                    D[0][j] = Math.max(D[1][j-2] ,  D[1][j-1]) + arr[0][j];
                    D[1][j] = Math.max(D[0][j-2] , D[0][j-1]) + arr[1][j];
                }
            }

            System.out.println(Math.max(D[0][n-1], D[1][n-1]));

        }
    }
}

자바 내장함수를 쓰지 않고, 8진수의 숫자 하나당 2진수의 세자리로 나타낼 수 있으니 (ex. 4 -> 110) 이를 이용해보고자 했다.

생각하지 못한 것

세자리를 맞추기 위해 앞에 0을 붙여도 보고, 배열도 거꾸로 돌려보고 이것저것 다 했지만, 결국 가장 기본적인것을 간과했다 🥲

8진수 0을 2진수 0으로 변환할 때 0 -> 000 이지만, 내가 while문을 잘못 쓰는 바람에 while문 자체가 동작을 하지 않았ㄷr ... ㅎㅎ (10 -> 1000이 되어야 하는데 1이 나옴)

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //Integer.toString(3);
        String octalString = br.readLine();
        String[] arr = {"000", "001", "010", "011", "100", "101", "110", "111"};

        if(octalString.equals("0")){
            System.out.println(0);
            return ;
        }

        StringBuilder binaryString = new StringBuilder();
        for(int i=0; i<octalString.length(); i++) {
            int n = octalString.charAt(i) - '0' ;
            String miniString = "";
            miniString += arr[n];
            // while(n != 0) {
            //     miniString += n%2;
            //     n /= 2;
            // }
            StringBuffer sb = new StringBuffer(miniString);

            if(sb.length() == 1) binaryString.append("00" + sb.toString()); // ("00" + sb.reverse().toString());
            else if(sb.length() == 2) binaryString.append("0" + sb.toString());
            else binaryString.append(sb.toString());
            //System.out.println(binaryString);

        }
        if (binaryString.charAt(0)=='0') binaryString.deleteCharAt(0);
        if (binaryString.charAt(0)=='0') binaryString.deleteCharAt(0);
        System.out.println(binaryString);
    }

}

아주 부끄럽지만 다시는 이런 실수를 하지 않기 위해 남긴다. 내가 구현력이 부족하다는 것을 다시한번 느낀 문제.. ㅠ ㅠ

✨ 우선순위큐는 사용되는 생성자에 따라 우선순위가 정해진다. (우선순위 큐에 Integer 자료형이 저장된다고 했을 때, 기본적으로 숫자가 작을수록 우선순위가 높다.)

PriorityQueue<Integer> queue = new PriorityQueue<>();

반대의 순서로 정렬하려면 다음과 같이 함수를 사용해주면 된다.

PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

✨ 탐색문제를 풀다보면 우선순위큐에 객체를 저장하는 경우가 있었다.

• 우선순위큐에 객체를 저장하려면 해당 객체의 클래스는 Comparable 인터페이스를 implements 해야한다.
• 해당 class 내에서 compareTo함수를 override하게 되는데, 이때 작성하는 *compareTo 함수내용에 따라 우선순위큐의 우선순위가 정해진다. *

//BOJ 6087 풀 때 사용한 class

class Mirror implements Comparable<Mirror>{
    int x, y, cnt, dir;

    Mirror(int x, int y, int cnt, int dir) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
        this.dir = dir;
    }

    @Override
    public int compareTo(Mirror m) {
        return this.cnt - m.cnt;
    }
}

1. 우선순위큐에 저장되는 객체를 위한 클래스(Mirror)는 Comparable을 구현한다.
   • Comparable : Mirror 객체와 다른 Mirror타입의 객체 비교
2. 생성자를 작성하는 것은 다른 클래스들과 다를 바가 없다.
3. 위의 코드의 경우에는 compareTo함수를 override할 떄 cnt를 기준으로해서 오름차순으로 우선순위가 정해진다. (즉, cnt가 작은 객체가 높은 우선순위)

   해당객체.some - 비교객체.some => 오름차순
   비교객체.some - 해당객체.some => 내림차순

bfs 탐색은 일반적으로 1,2,3,4,5,6 칸을 한다. 다만, 숫자가 100을 넘어가거나 방문을 했다면 skip 100에 도착했을 떄, 주사위 굴렸던 횟수를 출력한다. (100에 도착하지 못하는 경우는 없다고 한다)

이정도 ..?

생각하지 못한 것

뱀이나 사다리라면 해당 칸이 아니고 '해당 칸을 통해 이동되는 칸' 에 대해서 큐에 넣고 방문표시를 한다.

10x10이라고 해서, 숫자를 다시 이차원배열로 넣고 다시 숫자로 만드는 복잡한 과정을 거쳤는데, 검색해보니 그냥 일차원배열로 하는게 훠어얼씬 편해보였다.

코드

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

public class Main {
    static int[] board = new int[101];
    static int[] visited = new int[101];
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); //사다리 수
        M = Integer.parseInt(st.nextToken()); //뱀의 수

        Arrays.fill(visited, -1);

        for(int i=0; i<N+M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            board[start] = end;
        }

        bfs(1);
        //System.out.println(min);
    }

    static void bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] dx = {1, 2, 3, 4, 5, 6};
        queue.add(n);
        visited[n] = 0;

        while(!queue.isEmpty()) {
            int out = queue.poll();

            if(out == 100){
                System.out.println(visited[out]);
                return ;
            }


            //System.out.println(ox + " , " + oy + " -> " + out +  " / " +  (visited[ox][oy] + 1));
            for(int i=0; i<6; i++) {
                int nx = out+ dx[i];

                if(nx < 0 || nx > 100) continue;
                if(visited[nx] > -1 ) continue;
                if(board[nx] != 0) { //뱀이나 사다리인 경우
                    int num = board[nx];

                    if(visited[num] == -1) { //뱀이나 사다리로 이동하는 곳을 아직 방문하지 않았다면, 그곳을 큐에 넣는다.
                        queue.add(num);
                        visited[num] = visited[out] + 1;
                    }
                }
                //그냥 주사위 굴리는 중 
                else {
                    queue.add(nx);
                    visited[nx] = visited[out] + 1;
                }

            }
        }

    }

}

불을 먼저 bfs 탐색해서, 각 위치에 도착하는데 걸리는 시간을 구한다. 그 다음, 상근이를 bfs 탐색해서 탈출할 수 있을지 확인한다. 상근이 bfs탐색할 때 고려해야 하는 것은

• 상근이가 예전에 해당 위치를 방문했는지
• 상근이가 방문한 곳이 벽인지
• 상근이가 불과 동시 혹은 불보다 늦게 해당 위치를 방문했는지

생각하지 못한 것

• 상근이가 방문한 곳이 '불'인지
• 상근이가 불과 동시 혹은 불보다 늦게 방문한 경우 (불이 해당 위치를 아예 방문하지 않아서 그런 것은 아닌지, 즉 불의 방문 여부도 함께 고민)

코드

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

class Position{
    int x;
    int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main {
    static int T, w, h;
    static char[][] building;
    static boolean[][] visited, visited2;
    static int[][] dist, fireDist;
    static Queue<Position> queue = new LinkedList<>();
    static Queue<Position> queue2 = new LinkedList<>();
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            building = new char[h][w];
            //방문기록 초기화
            visited = new boolean[h][w];
            visited2 = new boolean[h][w];
            //거리 초기화
            dist = new int[h][w];
            fireDist = new int[h][w];

            for(int j=0; j<h; j++) {
                String str = br.readLine();
                for(int k=0; k<w; k++) {
                    building[j][k] = str.charAt(k);
                    if(building[j][k] == '*') {
                        queue.add(new Position(j, k));
                        visited[j][k] = true;
                    }
                    if(building[j][k] == '@') {
                        queue2.add(new Position(j, k));
                        visited2[j][k] = true;
                    }
                }
            }

            //먼저 불이 퍼져가는 시간 구하기 
            moveFire();

            escape();

            //queue 초기화
            queue = new LinkedList<>();
            queue2 = new LinkedList<>();

        }

    }

    static void moveFire() {
        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                else if(visited[nx][ny] || building[nx][ny] == '#') continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    fireDist[nx][ny] = fireDist[out.x][out.y] + 1;
                }
            }
        }
    }

    static void escape() { //불보다 늦게 도착할 때도 넘어가야쥐..
        boolean flag = false;

        while(!queue2.isEmpty()) {
            Position out = queue2.poll();

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    System.out.println(dist[out.x][out.y]+1);
                    flag = true;
                    return ;
                }
                else if(visited2[nx][ny] || building[nx][ny] == '#'|| building[nx][ny] == '*') continue;
                else if(fireDist[nx][ny]!= 0 && fireDist[nx][ny] <= dist[out.x][out.y]+1) continue;
                else {
                    queue2.add(new Position(nx, ny));
                    visited2[nx][ny] = true;
                    dist[nx][ny] = dist[out.x][out.y] + 1;
                }
            }

        }

        if(!flag)
            System.out.println("IMPOSSIBLE");
        return ;

    }

}

탐색할 수 있는 것 : 3가지 연산

1. 화면에 있는 이모티콘 복사해서 클립보드에 저장 => 이전 내용은 덮어진다.
2. 클립보드에 있는 이모티콘 화면에 붙여넣기
3. 화면에 있는 이모티콘 하나 삭제

• 화면에 이미 1개 있고, 3가지 연산만 사용해서 이모티콘 S개를 만들어야 한다.

클립보드에 있는 이모티콘 개수도 세어야하고, 화면에 있는 이모티콘 개수도 세어야할 것 같다

1. 초기값 : 화면에 1개, 클립보드 0개

-> 화면 복사 클립보드 저장 : 화면 1개, 클립보드 1개 -> 클립보드꺼 화면에 붙여넣기 : 화면 1개, 클립보드 0개 -> 화면 삭제 : 화면 0개, 클립보드 0개

화면 이모티콘 개수와 클립보드 이모티콘 개수, 그리고 시간(?)를 나타내는 class 만들어서 queue에 저장하기 queue에서 빼서 첫번째 연산하면 => 화면 그대로, 클립보드 : 화면 이모티콘 개수 , 시간+1 두번째 연산하면 => 화면 += 클립보드, 클립보드 그대로, 시간+1 세번째 연산 => 화면 -= 1, 클립보드 그대로, 시간+1

화면의 이모티콘 개수가 S개랑 같아지면, 그때의 시간을 출력하기

생각하지 못한 것

화면의 이모티콘 개수, 클립보드의 개수를 통해 방문여부를 점검하기

코드

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

class Emoticon {
    int screen; //화면에 있는 이모티콘 개수
    int board; //클립보드에 있는 이모티콘 개수
    int time; //현재까지의 시간

    Emoticon(int screen, int board, int time) {
        this.screen = screen;
        this.board = board;
        this.time = time;
    }
}

public class Main{
    static int S;
    static boolean[][] visited;
    static Queue<Emoticon> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = Integer.parseInt(br.readLine());

        visited = new boolean[10000][10000];
        queue.add(new Emoticon(1, 0, 0));
        visited[1][0] = true;
        bfs();

    }

    static void bfs() {

        while(!queue.isEmpty()) {
            Emoticon out = queue.poll();

            if(out.screen == S){
                System.out.println(out.time);
                return ;
            }

            if(out.screen > 0 && !visited[out.screen][out.screen]){

                queue.add(new Emoticon(out.screen, out.screen, out.time+1));
                visited[out.screen][out.screen] = true;
            }   
            if(out.board > 0 && !visited[out.screen + out.board][out.board]){
                queue.add(new Emoticon(out.screen + out.board, out.board, out.time+1));
                visited[out.screen + out.board][out.board] = true;
            }
            if(out.screen > 0 && !visited[out.screen -1][out.board]){
                queue.add(new Emoticon(out.screen-1, out.board, out.time+1));
                visited[out.screen -1][out.board] = true;
            }

        }
    }
}

• 아기 상어끼리의 안전거리 최댓값을 구한다고 생각했음

• 그래서 아기상어에서 다른 아기상어까지의 거리 중 최댓값을 구함

• But, 문제는 아기상어끼리의 최댓값이 아니고 특정 칸에서 아기 상어들과의 안전거리의 최댓값을 구하는 것이었음 => 즉, 상어가 있는 칸에서 bfs를 하는 것이 아님

• 상어가 없는 칸에서 안전거리를 구하고, 상어가 없는 모든 칸에서 안전거리를 다 구한 다음 안전거리의 최대값을 구한다.

  1. 0이고 아직 방문을 하지 않았을 떄, 안전거리를 구한다. (bfs 탐색)
  2. bfs탐색을 하다가 1을 만나면(=상어를 만나면) 그 때의 안전거리로 안전거리의 최대값을 업데이트 한다.
  3. bfs가 끝나면 방문여부를 다시 초기화 한다.

코드

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

class Position{
    int x;
    int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main {
    static int N, M, max = 0;
    static int[][] space, dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        space = new int[N][M];
        dist = new int[N][M];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dist[i], -1);
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(space[i][j] == 0 && dist[i][j] == -1){
                    bfs(i, j);

                    for(int k=0; k<N; k++)
                        Arrays.fill(dist[k], -1); //다시 업뎃
                }
            }

        }


        System.out.println(max);

    }

    static void bfs(int x, int y) {
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
        int[] dy = {0, -1, -1, -1, 0, 1, 1, 1};

        queue.add(new Position(x, y));
        dist[x][y] = 0;

        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<8; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || ny < 0 || nx >=N || ny >= M) continue;
                if(dist[nx][ny] >= 0) continue;
                queue.add(new Position(nx, ny));
                dist[nx][ny] = dist[out.x][out.y] + 1;

                if(space[nx][ny] == 1) { // 다른 아기 상어를 만났을 경우 
                    max = Math.max(max, dist[nx][ny]);
                    return ;
                }
            }
        }
    }

}

벽 부수고 이동하기 와 같은 로직으로 , _벽을 하나라도 부셨을 때_의 비용과 _하나도 부시지 않았을 때_의 비용을 구한다. 다만, 다른 점은 부실 수 있는 벽이 1개가 아니고 K개 이기 때문에 그동안 부신 벽의 개수와 K개를 비교해간다.

생각하지 못한 것

벽을 부셨는지, 부시지 않았는지가 아니라 몇개를 부셨는지를 통해 나타내야 한다. 벽의 개수가 K개보다 많아지는 상황도 고려해야 한다.

코드

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

class Wall {
    int x, y; //현재 map의 위치
    int cnt; //지금까지 부순 벽의 개수

    Wall(int x, int y, int cnt) {
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

public class Main {
    static int N, K, M;
    static int[][] map;
    static int[][][] dist; //거리를 나타냄
    static boolean[][][] visited; 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        dist = new int[N][M][12];
        visited = new boolean[N][M][12];


        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(Character.toString(str.charAt(j)));
            }
        }

        bfs(0, 0);

    }

    static void bfs(int x, int y) {
        Queue<Wall> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        boolean flag = false;

        if(map[x][y] == 0){ //벽이 아니면
            visited[x][y][0] = true;
            queue.add(new Wall(x, y, 0));

        } else {  //벽이면
            visited[x][y][1] = true;
            queue.add(new Wall(x, y, 1)); //

        }

        while(!queue.isEmpty()) {
            Wall out = queue.poll();

            if(out.x == N-1 && out.y == M-1 ){
                System.out.println(dist[out.x][out.y][out.cnt]+1);
                flag = true;
                return ;
            }

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;


                int cnt = out.cnt;
                if(map[nx][ny] == 1)  cnt++;
                if(visited[nx][ny][cnt] || cnt > K) continue;


                visited[nx][ny][cnt] = true;
                queue.add(new Wall(nx, ny, cnt));
                dist[nx][ny][cnt] = dist[out.x][out.y][out.cnt] + 1;


            }
        }

        if(!flag)
            System.out.println(-1);
    }

}

맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 곳(벽이 있는 곳)을 나타낸다. (1,1)에서 (N,M)까지 이동하려는데 (실제 배열에서는 0,0에서 N-1,M-1) 최단경로 구하기 한개의 벽을 부수는 것으로 경로가 짧아진다면 한개까지 부술 수 있음

1. 벽을 하나씩 깨보면서 그 때마다 최단 경로를 구해서 비교하기

• 벽을 하나씩 깨보면서(1일때마다) 해당 위치는 0으로 바꾸기 (이미 바꾸었다는 표시 해두기)
• 해당 경우의 탐색을 통해 최단 경로를 구하기
• 다시 1로 바꾸어 두기

생각하지 못한 것

벽을 하나씩 부수면 시간초과됨! 벽을 부수고 탐색하는 경우와 벽을 부수지 않고 탐색하는 경우를 나타내는 배열을 둔다. (3차원 배열을 사용한다.)

• dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
• dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함

코드

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

class Wall {
    int x, y; //현재 map의 위치
    boolean change; //지금까지 벽을 부순적 있는지

    Wall(int x, int y, boolean change) {
        this.x = x;
        this.y = y;
        this.change = change;
    }
}

public class Main {
    static int N, M, r_min = Integer.MAX_VALUE, min = Integer.MAX_VALUE;
    static int[][] map;
    static int[][][] dist; //거리를 나타냄
    static boolean[][][] visited; 
    static boolean flag ;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        dist = new int[N][M][2];
        visited = new boolean[N][M][2];

        int count = 0;

        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(Character.toString(str.charAt(j)));
            }
        }


        bfs(0, 0); 



    }

    static void bfs(int x, int y) {

        Queue<Wall> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};
        boolean flag = false;

        if(map[x][y] == 0){ //벽이 아니면
            visited[x][y][0] = true;
            queue.add(new Wall(x, y, false));

        } else {  
            visited[x][y][1] = true;
            queue.add(new Wall(x, y, true)); 

        }

        while(!queue.isEmpty()) {
            Wall out = queue.poll();

            if(out.x == N-1 && out.y == M-1){
                if(out.change)
                    System.out.println(dist[out.x][out.y][1] + 1);
                else
                    System.out.println(dist[out.x][out.y][0] + 1);

                flag = true;
                return ;
            }
            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                else if(map[nx][ny] == 0) { //벽이 아닐 때
                    if(!out.change && !visited[nx][ny][0]) { //벽을 부순적이 없다면
                        visited[nx][ny][0] = true;
                        queue.add(new Wall(nx, ny, out.change));
                        dist[nx][ny][0] = dist[out.x][out.y][0] + 1;
                    } 
                    if(out.change && !visited[nx][ny][1]) { //벽을 부순적이 있다면
                        visited[nx][ny][1] = true;
                        queue.add(new Wall(nx, ny, out.change));
                        dist[nx][ny][1] = dist[out.x][out.y][1] + 1;
                    }
                } 
                else if(map[nx][ny] == 1) { //벽일 떄
                    if(!out.change && !visited[nx][ny][0]) { //벽을 부순적이 없으면
                        visited[nx][ny][1] = true;
                        queue.add(new Wall(nx, ny, true));
                        dist[nx][ny][1] = dist[out.x][out.y][0] + 1;
                    }
                }
            }
        }

        if(!flag)
            System.out.println(-1);
    }


}

두 대륙을 연결하는 가장 짧은 다리 구하기

1. 서로 다른 대륙임을 어떻게 구분하는가 서로 다른 대륙임을 나타내는 배열을 하나 만든다.
2. 서로 다른 대륙임을 나타내는 배열에서 bfs를 진행. 일단 상하좌우 탐색했을 때 같은 숫자만 있으면 그냥 리턴(=다른 숫자가 하나라도 있으면 리턴x) / 다른 숫자를 만날떄까지 탐색해가기

• 방문했으면 넘어가기
• 현재 위치가 바다가 아니고, 서로 다른 대륙인 경우 현재까지의 거리를 리턴하기

생각하지 못한것

• 육지일때 bfs를 진행한다. (처음엔 바다일 때 bfs를 진행했다.)
• 현재 위치와 탐색을 시작한 위치가 같은 경우 넘어가주어야 한다.
• 현재 위치가 바다가 아니고, 서로 다른 대륙인 경우 현재까지의 최소거리를 구하고 리턴한다.
• 하나의 대륙에서 탐색이 끝나면 방문여부를 다시 초기화해주어야 한다.

코드

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

class Position{
    int x;
    int y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


public class Main{
    /*
     * 두 대륙을 연결하는 가장 짧은 다리 구하기
        1. 서로 다른 대륙임을 어떻게 구분하는가
            서로 다른 대륙임을 나타내는 배열을 하나 만든다. 
        2. 서로 다른 대륙임을 나타내는 배열에서 bfs를 진행. 일단 상하좌우 탐색했을 때 같은 숫자만 있으면 그냥 리턴(이 아니고 넘어가) || 이미 방문했으면 넘어가 || 배열의 범위를 벗어나면 넘어가 / 다른 숫자를 만날떄까지 탐색해가기

     */
    static int N, min = Integer.MAX_VALUE;
    static int[][] map, dist;
    static boolean[][] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        dist = new int[N][N];
        visited = new boolean[N][N];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int idx = 1;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                if(map[i][j] == 1 && !visited[i][j]){
                    makeIsland(i, j, idx);
                    idx++;
                }
            }
        }   


        //방문여부 초기화
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                visited[i][j] = false;
            }
        }

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(map[i][j] != 0){
                        bfs(i, j);
                    }
                }
            }

        System.out.println(min);


    }

    static void makeIsland(int x, int y, int idx) {
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        queue.add(new Position(x, y));
        visited[x][y] = true;
        map[x][y] = idx;

        while(!queue.isEmpty()) {
            Position out = queue.poll();
            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx<0 || ny<0 || nx >=N || ny >=N) continue;
                else if(visited[nx][ny] || map[nx][ny] == 0) continue;
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    map[nx][ny] = idx;
                }
            }
        }
    }

    static void bfs(int x, int y) { //육지를 무시해야하는거 아닐까 ,, (즉, 육지인 경우 그냥 넘어가) 바다인 경우만 탐색을 하다가 (거리를 구해가면서) (잔짜 아님,, 바다가 아닐 때 탐색) 육지를 만났을 때, 다른 육지라면, map[nx][ny] != 0 && map[x][y] != map[nx][ny] 일 때 그 최소거리를 구하는 것.. 
        Queue<Position> queue = new LinkedList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        queue.add(new Position(x, y));
        visited[x][y] = true;

        while(!queue.isEmpty()) {
            Position out = queue.poll();

            for(int i=0; i<4; i++) {
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nx<0 || ny<0 || nx >=N || ny >=N) continue;
                else if(visited[nx][ny] || map[x][y] == map[nx][ny]) continue; 
                else if(map[nx][ny] != 0 && map[x][y] != map[nx][ny]) {
                    min = Math.min(min, dist[out.x][out.y]);
                    //방문여부 초기화
                    for(int k=0; k<N; k++) {
                        for(int j=0; j<N; j++) {
                            visited[k][j] = false;
                        }
                    }
                    return ;
                }
                else {
                    queue.add(new Position(nx, ny));
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[out.x][out.y] + 1;
                }
            }

        }

        //방문여부 초기화
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                visited[i][j] = false;
            }
        }
    }
}

해당 풀이보다 시간복잡도를 낮추어서 풀 수 있는 방법도 있다고 한다. 더 공부하고 다시 정리해야겠다 !

현재 위치 X에서 할 수 있는 일

1. 1초 후, X-1 또는 X+1 로 이동
2. 0초 후, 순간이동 세 가지 경우를 고려하면서 순간이동할때만 시간 안더해주면 되지 않을까 ? 배열의 크기는 수빈이의 현재위치 * 2 +1로 정해둔다.

생각하지 못한 것

1. X-1 또는 X+1 이동과 순간이동의 가중치를 다르게 처리해주어야 한다는 것 (0-1 BFS 알고리즘이라고 한다.)
   • 순간이동하는 경우 queue의 맨 앞에 넣는다.
2. 수빈이의 위치와 동생의 위치를 비교할 때는 탐색하는 위치 (-1, +1 x2)가 아니라 현 위치로 비교해야 한다.
3. 탐색할 때, x2, -1, 1 순서로 탐색한다. (-1, 1 순서와 1, -1의 순서일 때 결과값 (가장 빠른 시간)이 달랐다. )
   • 탐색을 처음으로 할때만 시간을 업데이트 했기 때문인듯 !
   • 더 빨리 도착하는 방법이 나오면 다시 갱신 했음

코드

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

public class Main{
    static int N, K;
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 수빈이의 현재위치
        K = Integer.parseInt(st.nextToken()); // 동생의 현재위치

        visited = new boolean[200001];
        dist = new int[100001];

        bfs(N);
        //bfs2(N);
    }

    static void bfs(int curr) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(curr);
        visited[curr] = true;
        int min = Integer.MAX_VALUE;

        while(!queue.isEmpty()) {
            int out = queue.poll();

            if(out == K){
                System.out.println(dist[out]);
                return ;
            }

            int[] move = {out, -1, 1};

            for(int i=0; i<3; i++) {
                int next = out + move[i];

                if(next < 0 || next > 100000) continue;
                else if(visited[next]) continue;
                else {
                    if(i != 0) { //순간이동하는 경우 아니면
                        queue.offer(next);
                        visited[next] = true;
                        dist[next] = dist[out] + 1;

                    }
                    else { 
                        queue.addFirst(next);
                        visited[next] = true;
                        dist[next] = dist[out];

                    }

                }
            }
        }

        return ;
    }
}

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

public class Main {
    static int N, K;
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // 수빈이의 현재위치
        K = Integer.parseInt(st.nextToken()); // 동생의 현재위치

        visited = new boolean[100001];
        dist = new int[100001];


        bfs(N);
    }

    static void bfs(int curr) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(curr);
        visited[curr] = true;
        int min = Integer.MAX_VALUE;

        while(!queue.isEmpty()) {
            int out = queue.poll();
           // visited[out] = true;

            if(out == K){
                System.out.println(dist[out]);
                return ;
            }

            int[] move = {out,  1, -1};
            for(int i=0; i<3; i++) {
                int next = out + move[i];

                if(next < 0 || next > 100000) continue;
                else if( visited[next]) continue;
                else {
                    if(i != 0) { //순간이동하는 경우 아니면
                        queue.offer(next);
                        visited[next] = true;
                        if(dist[next] != 0)
                            dist[next] = Math.min(dist[next], dist[out]+1);
                        else
                            dist[next] = dist[out] + 1;
                    }
                    else { 
                        queue.addFirst(next);

                        visited[next] = true;
                        if(dist[next] != 0)
                            dist[next] = Math.min(dist[next], dist[out]);
                        else
                            dist[next] = dist[out];
                    }
                }

            }
        }

        return ;
    }
}

삼차원 배열 사용 익은 토마토가 여러개일 수 있음 => queue에 한번에 넣기 , 방문 표시 저장될 때부터 모든 토마토가 익어있는 상태라면 0을 출력해야 한다. bfs 시작하기 배열 길이를 벗어나거나, 이미 방문했거나, 토마토가 들어있지 않은 칸이라면 => 탐색된 위치에 있는 토마토들은 익어감

bfs를 한번 했는데 0인 토마토가 남아있다면 모두 익지 못하는 상황이다. ( -1 출력)

코드

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

public class Main {

    static int H, N, M;
    static boolean[][][] visited;
    static int[][][] tomatos;
    static int[][][] dist;
    static int days = 0;
    static Queue<Position2> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken()); 
        N = Integer.parseInt(st.nextToken()); 
        H = Integer.parseInt(st.nextToken()); 


        visited = new boolean[H][N][M];
        tomatos = new int[H][N][M];
        dist = new int[H][N][M];
        boolean flag = true;
        boolean complete = true;

        for(int i=0; i< H; i++) {
            for(int j=0; j< N; j++) {
                st = new StringTokenizer(br.readLine());
                for(int k=0; k<M; k++) {
                    tomatos[i][j][k] = Integer.parseInt(st.nextToken());  //  정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸

                    if(tomatos[i][j][k] == 0) 
                        flag = false; //익지 않은 것이 하나라도 있음
                    if(tomatos[i][j][k] == 1){
                        q.add(new Position2(i, j, k)); 
                        visited[i][j][k] = true;
                    }
                }
            }
        }

        // if(flag)
        //     return 0; //처음부터 다 익어있음 

        int count = 0;
        for(int i=0; i< H; i++) {
            for(int j=0; j< N; j++) {
                for(int k=0; k<M; k++) {
                    if(tomatos[i][j][k] == 1){
                        bfs(i, j, k); 
                    }
                }
            }
        }

        for(int i=0; i< H; i++) {
            for(int j=0; j< N; j++) {
                for(int k=0; k<M; k++) {
                    if(tomatos[i][j][k] == 0) {
                        complete = false;
                    }

                }
            }
        }

        //System.out.println(count + " ==================== ");
        if(flag)
            System.out.println(0);
        else if(!complete)
            System.out.println(-1);
        else{

            System.out.println(days);
        }
        //return count;
    }

    static void bfs(int h, int x, int y) {
        int[] dh = {0, 0, 0, 0, 1, -1};
        int[] dx = {-1, 0, 1, 0, 0, 0};
        int[] dy = {0, -1, 0, 1, 0, 0};

        while(!q.isEmpty()) {
            Position2 out = q.poll();

            for(int i=0; i<6; i++) {
                int nh = out.h + dh[i];
                int nx = out.x + dx[i];
                int ny = out.y + dy[i];

                if(nh< 0 || nx< 0 || ny< 0 || nh >= H || nx>= N || ny >= M ) continue;
                else if( visited[nh][nx][ny] || tomatos[nh][nx][ny] == -1 ) continue;
                else {
                    visited[nh][nx][ny] = true;
                    tomatos[nh][nx][ny]  = 1;
                    q.add(new Position2(nh, nx, ny));
                    dist[nh][nx][ny]  = dist[out.h][out.x][out.y] + 1;
                    days = dist[nh][nx][ny] ;
                }
            }

        }
    }

}

class Position2{

    int h;
    int x;
    int y;

    Position2(int h, int x, int y) {

        this.h = h;
        this.x = x;
        this.y = y;
    }
}

F : 사무실의 층수 G : 목적지의 위치(층수) S : 강호가 현재 있는 곳 U, D : 엘레베이터에 존재하는 버튼 (각각 위로 U층, 아래로 D층 이동)

현재 층에서 할 수 있는 것 : 위로 U층 또는 아래로 D층 이동한 층이 1층보다 아래거나, 사무실의 층수를 벗어나면 continue; 그렇지 않으면 탐색하는 층을 queue에 넣기 그러다 num[nx][ny] 가 G와 같으면 그때의 버튼 수 출력

1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 ...
                            -> 10 ...
                    -> 8 -> 10
                        -> 7
                -> 6 -> 8
                    -> 5
            -> 4 -> 6
                -> 3
        -> 2 -> 4
            -> 1

  -> 0 5 7 9 11 10

생각하지 못한 것

1. 현재 있는 곳과 목적지의 위치(층수)가 같을 때, use the stairs이 아닌 0이 출력되어야 한다.
2. 층수의 시작은 0이 아닌 1이다.

코드

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

public class Main {
    static int  F, S, G, U, D;
    static boolean[] visited;
    static int[] dist;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        F = Integer.parseInt(st.nextToken()); //전체 층수
        S = Integer.parseInt(st.nextToken()); //현재위치
        G = Integer.parseInt(st.nextToken()); //목적지 층수
        U = Integer.parseInt(st.nextToken()); //위로 갈 수 있는 층수
        D = Integer.parseInt(st.nextToken()); //아래로 갈 수 있는 층수
        visited = new boolean[F+1];
        dist = new int[F+1];
        if(S == G){
            System.out.println(0);
            return ;
        }
        bfs(S);

    }

    static void bfs(int x) {
        Queue<Integer> queue = new LinkedList<>();
        int[] move = {U, -D};
        queue.add(x);
        visited[x] = true;

        while(!queue.isEmpty()) {
            int out = queue.poll();

            for(int i=0; i<2; i++) {
                int next = out + move[i];

                if(next < 1 || next > F) continue;
                else if(visited[next]) continue;
                else {
                    queue.add(next);
                    visited[next] = true;
                    dist[next] = dist[out] + 1;
                    //System.out.println("dist[next] " + dist[next]);
                    if(next == G){
                        System.out.println(dist[next]);
                        return ;
                    }
                }

            }
        }

        System.out.println("use the stairs");
        return ;
    }

}