Root 계정

• AWS 계정 생성 시 사용하는 기본 계정
• 모든 AWS 서비스와 리소스에 대해 무제한 권한을 보유 => 최고 권한 사용자

IAM 사용자 계정

• Root 사용자가 생성하는 하위 사용자 계정
• 특정 권한만 부여받아 제한된 작업만 수행 가능
• 필요에 따라 AWS Management Console, CLI, API 접근 가능

계정의 생성

• Root 계정은 처음 AWS 계정을 생성할 때 자동으로 만들어지는 계정이다. AWS 계정을 새로 생성했다면 Root 계정을 이미 가지고 있는 것이다.

AWS의 권고사항을 보면, 루트 사용자를 일반적으로 사용하지 말 것을 강력하게 권고하고 있다. 즉, 루트 계정을 만들고 IAM 관리자 계정을 생성한 후 IAM 사용자로 이용해야 한다.

IAM 사용자 계정 생성

콘솔에서 IAM 검색 후 클릭

사용자 > 사용자 생성 클릭

* Adminstrator 관리자 계정 생성

• 관리자 역할을 부여할 사용자인 Administrator을 생성

권한설정에서 AdministratorAccess 선택 AdministratorAccess는 AWS 서비스와 리소스에 대한 최대 Access를 부여

태그 설정은 선택사항이라 넘어간다.

로그인 후 우측 상단에 Administrator@라고 뜨면 Administrator이라는 IAM 계정으로 접속했다는 뜻이다.

• 지금까지 했던 작업은 Administrator IAM 사용자가 AdministratorAccess 정책을 가지고 AWS의 모든 서비스와 리소스에 접근할 수 있게 했다. => 루트 사용자 대신 Administrator IAM 사용자로부터 관리 업무를 할 수 있게 한다.

* PowerUser IAM 계정 생성 [옵션]

• 지금부터는 모든 서비스에 액세스는 가능하지만 유저 관리는 할 수 없는 권한을 부여하는 사용자를 생성한다.

Administrator" 만들었던 방식과 동일하게 사용자 이름만 바꿔서 새로 사용자를 생성한다.

권한 정책에 PowerUserAccess를 선택한다. PowerUserAccess는 AWS 서비스와 리소스에 Full Access가 가능하지만, 사용자와 그룹에 대한 권한이 없는 정책이다.

IAM을 들어가보면 액세스가 거부됨을 확인할 수 있다.

Access Key, Secret Key 발급

• AWS 환경을 Terraform으로 생성하기 전에 Terraform 파일에서 사용할 Access Key와 Secret Key를 발급받아야 한다.
• Terraform이 클라우드 리소스를 생성, 관리, 삭제하는 데 필요한 권한을 얻기 위해 사용되는 IAM 자격 증명(Access Key와 Secret Access Key)을 설정해야 한다.

1. IAM 사용자로 로그인 ( Root 사용자 계정, Administrator 계정) Root 사용자 계정으로도 가능하다. 하지만 보안상 IAM 사용자로 로그인하는 것을 권장

2. IAM 대시보드로 이동 좌측 메뉴에서 사용자(Users)를 클릭

3. 대상 사용자 선택 Access Key를 생성할 IAM 사용자를 클릭

4. 사용자 상세 페이지에서 보안 자격 증명(Security Credentials) 탭 선택

5. 액세스 키 만들기 클릭

AWS 외부에서 실행되는 애플리케이션 선택

태그(선택사항) 입력

액세스 키, 비밀 엑세스 키(SecretK Key) 확인하고, 추후에 확인할 수 없으니 미리 *.cvs 파일 다운로드 하기

COUNT(칼럼명) : 갯수 SUM(칼럼명) : 합 AVG(칼럼명) : 평균 MIN(칼럼명) : 최솟값 MAX(칼럼명) : 최댓값 ABS(칼럼명) : 절댓값

문자열 함수

CONCAT("문자열1","문자열2") => 문자열1문자열2 : 문자열을 합치는 함수 LEFT : 문자에 왼쪽을 기준으로 일정 갯수를 가져오는 함수. => LEFT(문자, 가져올 갯수) MID : 문자에 지정한 시작 위치를 기준으로 일정 갯수를 가져오는 함수. = SUBSTRING,SUBSTR => MID(문자, 시작 위치, 가져올 갯수) RIGHT : 문자에 오른쪽을 기준으로 일정 갯수를 가져오는 함수. => RIGHT(문자, 가져올 갯수)

집계함수

ABS(숫자) : 절대값 CEIL(숫자) : 소수점 이하 올림 FLOOR(숫자) : 소수점 이하 버림 ROUND(숫자, 자릿수) : 자릿수를 기준으로 반올림 => 자연수는 0 TRUNCATE(숫자, 자릿수) : 자릿수를 기준으로 버림

날짜 함수

YEAR(날짜) : 범위 10009999까지에 대한 년을 반환합니다. MONTH(날짜) : 범위 112까지에 대한 월을 반환합니다. DATE(날짜) : 주어진 날짜, 시간의 날짜 부분을 반환합니다. => -> 2011-10-09

날짜 포맷함수

• DATE_FORMAT('날짜데이터', '출력날짜형식지정')

%Y 년도 (2021) %y 년도 (21)

%M 월 (January, August) %m 월 (01, 02, 11) %c 월 (1, 8) %b 월(Jan, Aug)

%D 일 (1st,2nd,3rd) %d 일(01, 19) %e 일(1, 19)

%W 요일(Wednesday, friday) %a 요일(Wed, Fri)

%T 시간 (12:30:00) %r 시간 (12:30:00 AM) %H 24시간 시간(01, 14, 18) %l 12시간 시간 (01, 02, 06)

%i 분 (00) %S 초 (00)

JOIN

SELECT A.column1, B.column2
FROM TableA A JOIN TableB B
ON A.common_column = B.common_column;

1. INNER JOIN 두 테이블에서 공통된 값을 기준으로 데이터가 결합됩니다. 일치하는 값이 있는 행만 반환
2. LEFT JOIN (또는 LEFT OUTER JOIN)
3. RIGHT JOIN 오른쪽 테이블의 모든 행을 반환하고, 왼쪽 테이블에서 일치하는 값이 없으면 NULL을 반환
4. FULL OUTER JOIN (MySQL에서 직접 지원하지 않음) 두 테이블의 모든 행을 반환하고, 일치하지 않는 값이 있는 경우 NULL을 반환합니다. MySQL에서는 FULL OUTER JOIN을 직접 지원하지 않지만, UNION을 사용하여 구현할 수 있습니다.
5. CROSS JOIN 두 테이블의 모든 가능한 조합을 반환
6. UNION 여러 개의 SELECT 문의 결과를 단일 결과 세트로 연결 표현할떄 사용

• 합친 결과에서 중복되는 행은 하나만 표시 => DISTINCT 키워드를 따로 명시하지 않아도 기본적으로 중복되는 레코드를 제거
• UNION 내의 각 SELECT 문은 같은 수의 열을 가져야 한다.
• 각각 SELECT 문의 열은 또한 동일한 순서로 있어야 한다.
• 열은 호환되는 데이터 형식을 가져야 한다

  SELECT * FROM A
  UNION  (ALL)      
  SELECT * FROM B

  

LIKE

문자열을 비교할 때 패턴 매칭을 사용하여 부분적인 일치 여부를 확인하는 데 사용

와일드카드 문자 %: 0개 이상의 임의의 문자와 일치. _: 정확히 1개의 임의의 문자와 일치.

NULL 함수

1. IFNULL : 해당 Column의 값이 NULL을 반환할 때, 다른 값으로 출력할 수 있도록 하는 함수 => IFNULL(Column명, "Null일 경우 대체 값")
2. ISNULL : 표현식1 의 결과값이 NULL 이면 표현식2의 값을 출력 => ISNULL(표현식1, "Null일 경우 대체 값")
3. IS NULL : NULL 값은 WHERE 절에서 찾을 수 없다, NULL 값을 찾을 때 사용

GROUP BY, HAVING

GROUP BY와 함께 사용되며, WHERE 절과 유사하지만, 중요한 차이점은 HAVING은 집계 함수에 대한 조건을 필터링이 가능하다.

GROUP BY USER_ID, PRODUCT_ID
HAVING COUNT(*) >= 2

ORDER BY, LIMIT

1. ORDER BY : 특정 열(컬럼)을 기준으로 결과 집합을 정렬합니다. => 기본적으로 오름차순(ASC)으로 정렬됩니다. 내림차순 정렬을 원할 경우 DESC 키워드를 사용

2. LIMIT : 결과 집합의 최대 행 수를 제한합니다. 주로 페이지네이션이나 대량 데이터 처리 시 사용

   SELECT name, age FROM users
   ORDER BY age DESC
   LIMIT 5;

   → age 기준으로 내림차순으로 정렬된 결과에서 상위 5개의 행만 반환

3. OFFSET : LIMIT와 함께 자주 사용되는 절로, 결과 집합에서 몇 개의 행을 건너뛸지를 지정

   SELECT name, age
   FROM users
   ORDER BY age ASC
   LIMIT 5 OFFSET 10;

   → age 기준으로 오름차순으로 정렬된 결과에서 10개의 행을 건너뛰고 그 다음 5개의 행만 반환

NULL 처리

• NULL AS : 특정 칼럼이나 표현식의 결과가 없을 때 NULL 값을 할당하기 위해 사용

  SELECT column1, NULL AS column2 FROM table_name;

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

.: 깨끗한 칸 *: 더러운 칸 x: 가구 o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다. 입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

예제 입력 1 * 7 5 ....... .o.... ....... ..... ....... 15 13 .......x....... ...o...x...... .......x....... .......x....... .......x....... ............... xxxxx.....xxxxx ............... .......x....... .......x....... .......x....... ......x...... .......x....... 10 10 .......... ..o....... .......... .......... .......... .....xxxxx .....x.... .....x... .....x.... .....x.... 0 0

*예제 출력 1 * 8 49 -1

풀이

1. 입력받을 때, 먼지리스트의 인덱스 0에는 청소기, 뒤에는 먼지 위치 넣기 => 청소기와 먼지 간의 거리 파악
2. BFS를 이용해 청소기, 먼지 들 간의 최소거리를 파악하는 배열을 만든다
3. DFS를 이용해 모든 먼지 칸을 방문해서 청소하는 최적의 거리를 파악한다.

public class Search_4991 {
    public static int N, M;
    // 북,남,서,동
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };
    public static int dust_cnt; // 먼지의 갯수 파악
    public static String[][] arr; // 위치배열
    public static int[][] dust_dis; // 먼지 간의 거리 파악하기 위한 배열
    public static Point[] dust_list; // 먼지정보를 담기위한 리스트
    public static boolean[] selected; // 리스트에 담긴 먼지들을 방문했는지 확인 배열 - DFS에서 사용
    public static int minMove;
    static class Point { // 위치 정보 클래스
        int x, y;

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true) { // 여러번 반복해서 입력을 받는다
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); //세로
            N = Integer.parseInt(st.nextToken()); //가로

            if (N == 0 && M == 0) break; // 입력받기 종료

            arr = new String[N][M]; // 전체 위치 배열

            dust_list = new Point[11]; // 청소기 + 먼지 갯수 최대 10개

            dust_cnt=1; // 0에는 청소기 위치가 들어간다. 인덱스 1부터 먼지 받기
            for (int i = 0; i < N; i++) {
                String str = br.readLine();
                String[] strArr = str.split("");
                for (int j = 0; j < M; j++) {
                    arr[i][j] = strArr[j];
                    if (arr[i][j].equals("o")) { // 0번은 무조건 로봇청소기
                        dust_list[0] = new Point(i, j);
                    } else if (arr[i][j].equals("*")) { // 그 뒤는 먼지
                        dust_list[dust_cnt++] = new Point(i, j);
                    }
                }
            } 

            minMove = Integer.MAX_VALUE;

            process();

            System.out.println(minMove);

        }
    }
    public static void process() {
        dust_dis = new int[dust_cnt][dust_cnt]; // 먼지 간의 거리 계산 배열

        for (int i = 0; i < dust_cnt; i++) { // 먼지의 수만큼 반복
            for (int j = i + 1; j < dust_cnt; j++) {
                int res = BFS(dust_list[i], dust_list[j]); // 서로의 먼지끼리 거리가 얼마나 되는지 계산
                if (res == -1) { // 도달할 수 없는 먼지가 있는 경우 더이상 반복 x
                    minMove = -1;
                    return;
                } else { // 반대에서 오는 경우도 잘 저장해주자
                    dust_dis[i][j] = dust_dis[j][i] = res;
                }
            }
        }

        // DFS에서 모든 먼지를 거쳐 최소거리를 찾는 방법을 구함
        selected = new boolean[dust_cnt];
        DFS(0, 0, 0);
    }

    // 먼지 간의 서로 거리 계산하기
    public static int BFS(Point start, Point end) {
        int[][] visited = new int[N][M]; //먼지 방문 배열
        Queue<Point> que = new LinkedList<Point>();
        que.offer(start);
        visited[start.x][start.y] = 1; // 시작점 체크

        int move = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            for (int s = 0; s < size; s++) { // 거리별 탐색
                Point now = que.poll();
                int x = now.x;
                int y = now.y;

                if ( x == end.x && y == end.y) {
                    return move; // 다른 먼지에 도착했을 때 몇번 움직였는지 리턴
                }

                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d];
                    int ny = y + dy[d];
                    if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

                    // 방문했거나 벽이면 넘어가기
                    if(visited[nx][ny]==1 || arr[nx][ny].equals("x")) continue;    
                    que.offer(new Point(nx, ny));
                    visited[nx][ny] = 1; // 방문체크
                }
            }
            move++;
        }

        // 도달 불가
        return -1;
    }

    // 모든 먼지를 방문해 청소하는 최고 거리를 찾는다.
    public static void DFS(int idx, int cnt, int sum) {
        if (cnt == dust_cnt-1) { // 모든 곳 방문
            minMove = Math.min(minMove, sum); // 최솟거리 계산
            return;
        }
        for (int i = 1; i < dust_cnt; i++) {
            if (selected[i]) continue;
            selected[i] = true;
            DFS(i, cnt + 1, sum + dust_dis[idx][i]);
            selected[i] = false;
        }
    }
}

* BFS(먼지들 간 거리 계산), DFS(거리배열에서 최소값 찾기) 혼합 사용

문제

많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다.

• 명령 1. Go k: k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.
• 명령 2. Turn dir: dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다.

공장 내 궤도가 설치되어 있는 상태가 아래와 같이 0과 1로 이루어진 직사각형 모양으로 로봇에게 입력된다. 0은 궤도가 깔려 있어 로봇이 갈 수 있는 지점이고, 1은 궤도가 없어 로봇이 갈 수 없는 지점이다. 로봇이 (4, 2) 지점에서 남쪽을 향하고 있을 때, 이 로봇을 (2, 4) 지점에서 동쪽으로 향하도록 이동시키는 것은 아래와 같이 9번의 명령으로 가능하다. 로봇의 현재 위치와 바라보는 방향이 주어졌을 때, 로봇을 원하는 위치로 이동시키고, 원하는 방향으로 바라보도록 하는데 최소 몇 번의 명령이 필요한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공장 내 궤도 설치 상태를 나타내는 직사각형의 세로 길이 M과 가로 길이 N이 빈칸을 사이에 두고 주어진다. 이때 M과 N은 둘 다 100이하의 자연수이다. 이어 M줄에 걸쳐 한 줄에 N개씩 각 지점의 궤도 설치 상태를 나타내는 숫자 0 또는 1이 빈칸을 사이에 두고 주어진다. 다음 줄에는 로봇의 출발 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 마지막 줄에는 로봇의 도착 지점의 위치 (행과 열의 번호)와 바라보는 방향이 빈칸을 사이에 두고 주어진다. 방향은 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어진다. 출발지점에서 도착지점까지는 항상 이동이 가능하다.

출력

첫째 줄에 로봇을 도착 지점에 원하는 방향으로 이동시키는데 필요한 최소 명령 횟수를 출력한다.

*예제 입력 1 * 5 6 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 4 2 3 2 4 1

*예제 출력 1 * 9

풀이

1. dx, dy, 방향 (동 -> 서 -> 남 -> 북) 3차 방문 배열
2. 1. dx, dy, 방향, 명령횟수 클래스 작성
3. BFS 사용 => 사방전파
4. 1. 전진이동 (1~3칸 이동)
5. 1.1. x,y축 방향*칸의 갯수대로 이동
6. 1.2. 중간에 벽이 있으면 더 이상 전진 못함
7. 1.3. x,y,방향의 방문배열 값이 0이면 방문 체크
8. 2. 회전 : right, left 변수로 오른쪽, 왼쪽 돌면 무슨 방향이 나오는지 바꾸기

public class Search_1726 {
    public static int N, M;
    public static int[][] arr; // 위치배열
    public static int[][] cnt; // 횟수배열
    public static int[][][] visited; // 방문배열 - 방향까지 작성
    public static Queue<Point> que = new LinkedList<Point>();
    public static int sx, sy, sd, ex, ey, ed;
    // 동, 서 , 남, 북
    public static int[] dx = { 0, 0, 1, -1 }; 
    public static int[] dy = { 1, -1, 0, 0 };

    public static class Point {
        public int x;
        public int y;
        public int d; // 방향
        public int cnt; // 각 위치에 도달하기 위한 명령 횟수
        public Point(int x, int y, int d, int cnt) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.cnt = cnt;
        }

    }

    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());

        arr = new int[N][M];
        cnt = new int[N][M];
        visited = new int[N][M][4]; // x축, y축, 방향

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

        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken())-1;
        sy = Integer.parseInt(st.nextToken())-1;
        sd = Integer.parseInt(st.nextToken())-1;

        st = new StringTokenizer(br.readLine());
        ex = Integer.parseInt(st.nextToken())-1;
        ey = Integer.parseInt(st.nextToken())-1;
        ed = Integer.parseInt(st.nextToken())-1;

        BFS();

    }
    public static void BFS() {
        // 시작위치, 방향, 명렬횟수 큐에 넣기
        que.offer(new Point(sx, sy, sd, 0));
        visited[sx][sy][sd] = 1; // 첫방문

        while (!que.isEmpty()) {
            Point now = que.poll();

            // 목적지에 방향까지 일치하면 사용된 명령횟수 출력하고 종료
            if(now.x==ex && now.y==ey && now.d==ed) {
                System.out.println(now.cnt);
                return;
            }

            // 1칸~3칸까지 전진이동 가능
            for(int i=1; i<=3; i++) {

                // 바라보는 방향으로 주어진 칸에 따라 전진이동
                int nx = now.x + dx[now.d]*i;
                int ny = now.y + dy[now.d]*i;

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (arr[nx][ny]==1) break; // 한칸씩 나아가면서 중간에 벽이 있으면 앞으로 진행 불가

                if(visited[nx][ny][now.d]==0) { //방문한 적이 없는 위치와 방향이면
                    visited[nx][ny][now.d] = 1; // 방문체크

                    // 방향과 명령횟수는 기존의 것 계속 이어서 사용
                    que.offer(new Point(nx, ny, now.d, now.cnt+1));
                }

            }


            int left = 0; 
            int right = 0;

            // 동서남북에서 왼쪽으로 돌렸을 때 방향, 오른쪽으로 돌렸을 떄 방향 검사
            switch(now.d) {
                // 동 왼쪽: 북, 오른쪽: 남
                case 0: left=3; right=2; break;
                // 서 왼쪽: 남, 오른쪽: 북
                case 1: left=2; right=3; break;
                // 남 왼쪽: 북, 오른쪽: 남
                case 2: left=0; right=1; break;
                // 북 왼쪽: 북, 오른쪽: 남
                case 3: left=1; right=0; break;
            }

            // 현재방향에서 왼쪽으로 돌았을 때 방문 체크
            if(visited[now.x][now.y][left]==0) {
                visited[now.x][now.y][left] = 1;
                que.offer(new Point(now.x, now.y, left,now.cnt+1 ));
            }
            // 현재방향에서 오른쪽으로 돌았을 때 방문 체크
            if(visited[now.x][now.y][right]==0) {
                visited[now.x][now.y][right] = 1;
                que.offer(new Point(now.x, now.y, right,now.cnt+1 ));

            }
        }

        // 목적지 찾을 수 없으면 -1
        System.out.println(-1);
    }


}

* BFS 사용

* 클래스에 기존 값을 넣어가면서 값을 계속해서 이어나간다. => 방향, 명령횟수

문제

홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 있어 홍익이가 탈출하기 어렵게 하고 있다.

홍익이는 마법사의 연구실에서 훔친 지팡이가 있어, 벽을 길로 만들 수 있다. 그렇지만, 안타깝게도 마법의 지팡이는 단 한 번만 사용할 수 있다.

이때, 홍익이를 도와 미로에서 탈출할 수 있는지 알아보고, 할 수 있다면 가장 빠른 경로의 거리 D는 얼마인지 알아보자.

인접한 칸으로 이동하는데 똑같은 시간이 들고, 벽을 부수는 데 시간이 걸리지 않는다.

입력

N M Hx Hy Ex Ey N X M 행렬

2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000 1 ≤ Hx, Hy, Ex, Ey ≤ 1000 (Hx, Hy)≠ (Ex, Ey) 행렬은 0과 1로만 이루어져 있고, 0이 빈 칸, 1이 벽이다.

출력

D (탈출 할 수 없다면, -1을 출력한다.)

*예제 입력 1 * 5 6 1 1 5 6 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0

*예제 출력 1 * 11

풀이

1. 3차 방문배열과 클래스를 만들어 x축, y축, 점프마법 사용여부 체크
2. 위치가 벽이면 아직까지 마법을 사용 안했고, 방문하지 않았다면 마법써서 탈출
3. 위치가 벽이 아니면 마법 사용안해도 되서 마법 사용여부 확인 안하고 방문체크 => 클래스에 기존 방문여부를 넣어가면서 마법 사용여부를 이어간다.

public class Search_14923 {
    public static int N, M, Hx, Hy, Ex, Ey;
    public static int[][] map; // 위치배열
    public static int[][][] visited; // 3차 방문배열 => x,y축, 마법 사용여부
    public static Queue<Point> que = new LinkedList<Point>();
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };
    public static int minTime = Integer.MAX_VALUE;

    public static class Point {
        public int x;
        public int y;
        public int jump; // 마법사용여부

        public Point(int x, int y, int jump) {
            this.x = x;
            this.y = y;
            this.jump = jump;
        }
    }

        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];
        visited = new int[N][M][2];

        st = new StringTokenizer(br.readLine());
        Hx = Integer.parseInt(st.nextToken()) - 1;
        Hy = Integer.parseInt(st.nextToken()) - 1;

        st = new StringTokenizer(br.readLine());
        Ex = Integer.parseInt(st.nextToken()) - 1;
        Ey = Integer.parseInt(st.nextToken()) - 1;

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

        BFS();

        if (minTime == Integer.MAX_VALUE)
            System.out.println(-1);
        else
            System.out.println(minTime);

    }

    public static void BFS() {
        que.offer(new Point(Hx, Hy, 0));

        // 시작점은 각각의 위치와 마법 사용했을 때, 안했을 때 둘 다 체크
        visited[Hx][Hy][0] = 1;
        visited[Hx][Hy][1] = 1;

        int second = 0;

        //반복문을 한번 돌 때마다 시간이 1초씩 흐른다.
        while (!que.isEmpty()) {
            second++;
        // System.out.println(second);

            int len = que.size();
            for (int s = 0; s < len; s++) {
                Point now = que.poll();

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

                    // 탈출위치면 리턴
                    if (nx == Ex && ny == Ey) {
                        minTime = second;
                        return;
                    }
                    if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                        continue;
                    // 벽
                    if (map[nx][ny] == 1) {
                        // 아직까지 마법을 사용 안했고, 방문하지 않았다면 마법써서 탈출
                        if (now.jump == 0 && visited[nx][ny][1] == 0) {
                            que.offer(new Point(nx, ny, 1));
                            visited[nx][ny][1] = 1; // 위치에서 마법 사용함
                        }
                    }
                    // 빈칸
                    else {
                        // 벽이 아니라 마법 사용안해도 되서 마법 사용여부 확인 안함
                        if (visited[nx][ny][now.jump] == 0) {
                            que.offer(new Point(nx, ny, now.jump));
                            visited[nx][ny][now.jump] = 1; // 마법사용여부 전에와 같이 유지
                        }
                    }
                }
            }
        }
    }
}

* BFS 사용

* 방문 3차 배열 - 가로, 세로, 마법 사용여부

* 클래스에 기존 값을 넣어가면서 값을 계속해서 이어나간다. => 마법사용여부

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

*예제 입력 1 * 3 3 DDD DDD DDD

*예제 출력 1 * 9

*예제 입력 2 * 3 3 RRD RDD ULL

*예제 출력 2 * 0

풀이

1. 하나씩 배열 돌면서 검사 => DFS로 밑으로 내려가기
2. 범위 벗어나면 탈출 성공 true
3. 1. 기억배열에서 T면 전에 탈출 가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 성공을 파악할 수 있다
4. 2. 기억배열에서 F면 전에 탈출 불가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 실패를 파악할 수 있다
5. 3. 방문했던 곳인데 기억 배열에 T,F 적용안되어 있으면 false
6. 위에 조건 다 통과하고 새로 방문한 곳이면 방문체크
7. 조건에 맞는 DFS 내려가기
8. 기억배열에 탈출 실패여부 정리
9. 탈출 여부 리턴

public class Search_17090 {
    public static int N, M;
    public static String[][] map; // 기억배열 
    public static int[][]  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()); 

        map = new String[N][M];
        visited = new int[N][M];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            String[] strArr = str.split("");
            for(int j = 0; j < M; j++) {
                map[i][j] = strArr[j];
            }
        }

        int count = 0; //시도 횟수
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(DFS(i,j)) count++;
            }
        }

        System.out.println(count);
    }

     public static boolean DFS(int x, int y) {
/*                                              
        // 각 DFS에서 위치에 대한 memorization 배열과 방문 배열 확인         
         System.out.println(x+","+y+"==============================================");
        System.out.println(x+"----------------------------------"+y);
        for (int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        System.out.println(x+"----------------------------------"+y);
            for (int i = 0; i < N; i++) {
                for(int j = 0; j < M; j++) {
                    System.out.print(visited[i][j]);
                }
                System.out.println();
            }
        System.out.println("==============================================");
*/

        boolean result = false; // 처음에는 false로 초기화

        if (x<0 || y<0 || x>=N || y>=M ) return true; // 범위 넘어가면 탈출 성공
        // 기억배열에서 T면 전에 탈출 가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 성공을 파악할 수 있다
        if (map[x][y].equals("T")) return true; 
         // 기억배열에서 F면 전에 탈출 불가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 실패를 파악할 수 있다
        else if (map[x][y].equals("F")) return false;

        // 방문했던 곳인데 기억 배열에 T,F 적용안되어 있으면 false 
        if (visited[x][y]==1) return false;

        // 위에 조건 다 통과하고 새로 방문한 곳이면 방문체크
        visited[x][y] = 1;

        // 조건에 맞는 DFS 내려가기
        if (map[x][y].equals("U")) result = DFS(x-1,y);
        else if (map[x][y].equals("R")) result = DFS(x,y+1);
        else if (map[x][y].equals("L")) result = DFS(x,y-1);
        else if (map[x][y].equals("D")) result = DFS(x+1,y);

        // 기억배열에 탈출 실패여부 정리
        map[x][y] = result? "T" : "F";

        // 탈출 여부 리턴
        return result;
    }
}

* DFS 사용

* 기억 배열사용해서 시간 절약하기

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다.

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

예제 입력 1 * 3 3 D. ... .S.

*예제 출력 1 * 3

예제 입력 2 * 3 3 D. ... ..S

*예제 출력 2 * KAKTUS

풀이

• 방문배열 : 0 - 빈칸, 1 - 고슴도치, 2 - 물, 3 - 벽

1. 동물 큐, 물 큐 분리 / 위치배열, 방문배열, 시간배열은 통합
2. 입력받을 때 시작점, 도착점 위치 저장 => BFS 매개변수로 입력
3. 1. 물(*) 입력 받을 때 물 큐에 위치 넣기
4. 2. 돌(X) 입력 받을 때 방문배열(visted) 3으로 수정
5. BFS에서 시작점 큐에 넣고 방문체크
6. 1. while문 돌 때마다 1초씩 지난다 => 동물 먼저 이동 후 물 확산
7. 동물이동
8. 1. 다음 이동이 물이면 지나가지 못함 => 넘어가기
9. 2. 다음 이동이 돌이나 물이 아니거나, 방문하지 않았던 곳이라면 이동 => 시간배열, 방문배열, 큐 체크
10. 3. 만약 비버네에 도착했으면 시간 계산후 리턴
11. 물 확산
12. 1. 사방 확인해서 이동할 곳이 돌이 아니거나, 벽이 아니거나 비버집이 아니면 물이 참 => 위치배열, 방문배열, 시간배열, 큐 체크

public class Search_3055 {
    public static int N, M;
    public static String[][] arr; // 위치배열
    public static int[][] time; // 고슴도치가 각 위치에 도달하는 시간
    public static Queue<Point> animalQueue = new LinkedList<>(); // 동물이동 큐
    public static Queue<Point> waterQueue = new LinkedList<>(); // 물 확산 큐
    public static int[][] visited; // 방문 위치 배열
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };
    public static int minTime = Integer.MAX_VALUE;

    public static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    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());

        arr = new String[N][M]; //위치배열
        time = new int[N][M]; //시간배열
        visited = new int[N][M]; //방문 배열

        Point start = null, finish = null;
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            String[] strArr = str.split("");
            for(int j = 0; j < M; j++) {
                arr[i][j] = strArr[j];
                if(arr[i][j].equals("S")) { //시작
                    start = new Point(i,j);
                }else if(arr[i][j].equals("D")) { //도착
                    finish = new Point(i,j);
                }else if(arr[i][j].equals("*")) { //물
                    waterQueue.offer(new Point(i,j)); // 물 큐에 모든 물 위치 넣기
                    visited[i][j] = 2; //물
                }else if(arr[i][j].equals("X")) { //돌
                    visited[i][j] = 3; //돌
                }
            }
        }

        BFS(start, finish); //확산 - 고슴도치, 물

        if(minTime==Integer.MAX_VALUE) System.out.println("KAKTUS");
        else System.out.println(minTime);

    }

    public static void BFS(Point start, Point finish) {

        animalQueue.offer(start); //동물 큐에 동물 시작위치 넣기
        visited[start.x][start.y] = 1; // 동물 방문

        // 반복문이 한번 돌 때마다 1초씩 지난다 => 동물먼저이동, 물 확산
        while(!animalQueue.isEmpty()) {

            // 각 시간마다 고슴도치의 시작 위치 파악해 계산
               // 위에서 고정을 해야한다 => 코드의 흐름에 따라 고슴도치의 시작점이 많이지거나 적어질 수 있다.
            int minutes = animalQueue.size();
            for (int s = 0; s < minutes; s++) {
                Point now = animalQueue.poll();

                // 물이면 지나가지 못함 - 넘어가기
                if (arr[now.x][now.y].equals("*")) continue;

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

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

                    // 이동할 곳이 돌이거나 물이 아니면 이동
                    if (!(arr[nx][ny].equals("X")||arr[nx][ny].equals("*"))) {
                        if (visited[nx][ny]==0) {
                            time[nx][ny] = time[now.x][now.y]+1; //시간배열 증가

                            // 다음에 비버네 도착
                            if (nx == finish.x && ny == finish.y) {
                                checkTime();
                                return;
                            }

                            visited[nx][ny] = 1; //고슴도치 이동했던 곳 체크
                            animalQueue.offer(new Point(nx, ny)); //새로운 시작점 넣기
                        }
                    }   
                }
            }
            // 고슴도치 먼저 이동 후에 물 이동하기
            waterFlow();
        }


    }
    // 비버네 도착했을 떄 시간 파악
    public static void checkTime() {
        int maxtime =0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                maxtime = Math.max(maxtime, time[i][j]);
            }
        }
        minTime = Math.min(maxtime, minTime);
    }
    // 물 확산 확인
    public static void waterFlow() {
        int sameMinutes = waterQueue.size();
        for (int s = 0; s < sameMinutes; s++) {
            Point now = waterQueue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

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

                // 이동할 곳이 돌이 아니거나, 벽이 아니거나 비버집이 아니면 물이 참
                if (!(arr[nx][ny].equals("X")||arr[nx][ny].equals("D")||arr[nx][ny].equals("*"))) {
                        arr[nx][ny] = "*";
                        visited[nx][ny] = 2; //물 위치 체크
                        time[nx][ny] = 0; //고슴도치가 도달했던 곳에 물이 차서 시간 필요 없어짐
                        waterQueue.offer(new Point(nx, ny));

                }
            }
        }

    }




}

* BFS 사용

* 두가지의 큐, 배열의 통합

* 선후관계 파악 (동물 -> 물)

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 활성 상태로 변경한 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 비활성 바이러스는 *, 활성 바이러스는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

* 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 *

시간이 최소가 되는 방법은 아래와 같고, 4초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 * - 3 2 3 4 *

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(4 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 비활성 바이러스의 위치이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

*예제 입력 1 * 7 3 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

*예제 출력 1 * 4

*예제 입력 2 * 5 1 2 2 2 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 2 2 1 1

*예제 출력 2 * 0

* 바이러스 위치는 고정되었고, 놓아진 자리에 바이러스를 활성화 시킬것인지 아닌 것인지 파악 => 이 자리는 빈칸 취급을 하지 않는다.

* 모든 빈칸에 바이러스가 놓아지는 최소 시간

풀이

1. 입력받을 때 0(빈칸) 갯수 세기(originEmptySpace), 2(바이러스)위치는 list에 넣기
2. 1. 빈칸의 갯수가 0이면 더 이상 퍼질 바이러스 공간이 없다 => 진행x, 진행 시간 0
3. 2. 조합을 위한 바이러스 체크 배열을, list의 크기만큼 인덱스 크기를 지정해 초기화 => check
4. DFS를 이용해 바이허스를 활성화 시키는 조합 구성
5. 1. 지정된 활성 갯수에 도달하면 BFS 호출에 바이러스 확산 확인
6. 2. check배열을 넣고 빼면서 DFS 내려가기
7. BFS로 활성화된 바이러스의 확산을 파악하기
8. 1. 현재 위치 배열에 영향을 끼치지 않게 깊은 배열 복사로, 복사 배열을 형성한다.
9. 2. 얼마나 많은 빈칸이 점염됬는지 파악하는 count 변수 생성 => 빈칸(0)이 바이러스(3)으로 수정되면 하나씩 증가
10. 3. 바이러스 넣은 곳 큐에 넣고, 방문(visted)배열 체크, 복사위치배열에 바이러스 활성화 체크 ( * -> 3)
11. 4. 사방돌면서 벽(1)이면 넘어가고, 빈칸(0)이거나 비활성화 바이러스(2) 확산시간 증가, 활성바이러스 위치체크, 확산방문 체크
12. 5. 만약 빈칸(0)이면 count++해 점염된 빈칸의 갯수를 줄인다.
13. 6. 남은 빈칸이 없어지고 모두 확산됬으면 빠져나오기 (count==originEmptySpace)
14. 시간 배열에서 가장 값이 높은 수가 바이러스가 마지막에 확신된 시간이다. => 이것의 최솟값 찾기

public class Search_17142 {
    public static int N, M;
    public static int[][] arr;
    public static int originEmptySpace = 0; // 빈칸
    public static ArrayList<Point> list; // 바이러스 놓아진 위치 파악
    public static int[] check; // 바이러스 놓아진 위치에서 활성화 체크할 배열
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };
    public static int minTime = Integer.MAX_VALUE;

    public static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    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());

        arr = new int[N][N];
        list = new ArrayList<Point>();

        originEmptySpace = 0; // 벽과 바이러스 위치가 아닌 빈칸 위치 파악하기 위한 변수

        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());
                if(arr[i][j]==2) list.add(new Point(i,j)); // 바이러스 위치 저장
                else if(arr[i][j]==0) originEmptySpace++; // 빈칸
            }
        }
        if(originEmptySpace==0) { //빈칸이 0이면 더 이상 퍼질 바이러스 공간이 없다 => 0
            System.out.println(0);
            System.exit(0);
        }

        check = new int[list.size()]; // 활성화 바이러스 체크 여부

        DFS(0, 0);

        if(minTime==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(minTime);

    }

    public static void DFS(int start, int cnt) {
        //먼저 바이러스를 놓을 수 있는 k개의 위치 중 m개의 위치를 선정해야 한다. 이는 조합으로 나타낼 수 있다.
        if(cnt==M) {
            BFS(); //바이러스 다 놓았다면 확산 확인
            return;
        }else {
            for(int i=start; i<list.size(); i++) {
                check[i] = 1;
                DFS(i + 1, cnt+1);
                check[i] = 0;
            }
        }
    }

    public static void BFS() {
        // 깊은 복사
        int[][] copy_arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            copy_arr[i] = arr[i].clone();
        }

        // 경우의 수마다 새로 초기화
        int[][] time = new int[N][N]; //확산 시간 파악
        int[][] visited = new int[N][N]; //학산 여부 파악
        Queue<Point> que = new LinkedList<>();

        for(int i=0; i<list.size(); i++) {
            if(check[i]==1) { // 바이러스 활성화 시킨 곳
                Point po = list.get(i);
                copy_arr[po.x][po.y]=3; // 복사 위치배열에 활성화 체크
                que.offer(new Point(po.x,po.y)); // 큐에 시작점 넣기
                visited[po.x][po.y]=1; // 바이러스를 놓아 확산된 곳
            }
        }

        /*
        // 확산되기 전 배열 확인 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(copy_arr[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        */        

        int count = 0; // 점염되지 않은 남은 빈칸 확인하기 위해

        while(!que.isEmpty()) {
            Point now = que.poll();
            int x = now.x; // 현재 값
            int y = now.y; 

            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0<=nx && nx<N && 0<=ny && ny<N) {
                    if(visited[nx][ny]==1)continue; // 벽이면 넘어가기
                    if(copy_arr[nx][ny] == 0) { // 빈칸이면
                        time[nx][ny] = time[x][y]+1; // 확산 시간 증가
                        if(time[nx][ny]>minTime) return; // 최소시간 보다 크면 계산 필요x => 시간 절약
                        que.offer(new Point(nx,ny));
                        copy_arr[nx][ny] = 3; // 활성 바이러스 체크
                        visited[nx][ny]=1; // 확산 체크

                        count++;
                    }else if(copy_arr[nx][ny] == 2) { // 비활성화 바이러스 위치
                        time[nx][ny] = time[x][y]+1; // 확산 시간 증가
                        if(time[nx][ny]>minTime) return;  // 최소시간 보다 크면 계산 필요x => 시간 절약
                        que.offer(new Point(nx,ny));
                        copy_arr[nx][ny] = 3; // 활성 바이러스 체크
                        visited[nx][ny]=1;   // 확산 체크
                    }
                }
            }
            //남은 빈칸이 없어지고 모두 확산됬으면 빠져나오기
            if(count==originEmptySpace) {
                break;
            }
        }
        /*
        // 바이러스가 확산되고난 후 확인 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(time[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println();
        */ 

        int maxtime =0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(copy_arr[i][j]==0) { // 아직 확산되지 않은 공간 있으면 실패
                    return;
                }
                // 가장 값이 높은 수가 바이러스가 마지막에 확신된 시간이다.
                maxtime = Math.max(maxtime, time[i][j]);
            }
        }
        //System.out.println("-----------------"+maxtime);
        minTime = Math.min(maxtime, minTime);

    }


}

* 그냥 빈칸과 바이러스 존의 차이점을 파악하고 빠른 처리를 위해 조치 (originEmptySpace, count 변수)

* DFS로 경우의 수 찾고, BFS 확산에 사용

* 초기 여러 곳의 값을 저장할 때 리스트 사용

문제

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다.

연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

M = 3이고, 바이러스를 아래와 같이 놓은 경우 6초면 모든 칸에 바이러스를 퍼뜨릴 수 있다. 벽은 -, 바이러스를 놓은 위치는 0, 빈 칸은 바이러스가 퍼지는 시간으로 표시했다.

6 6 5 4 - - 2 5 6 - 3 - 0 1 4 - - 2 - 1 2 3 - 2 1 2 2 3 2 2 1 0 1 - - 1 - 2 1 2 3 4 0 - 3 2 3 4 5

시간이 최소가 되는 방법은 아래와 같고, 5초만에 모든 칸에 바이러스를 퍼뜨릴 수 있다.

0 1 2 3 - - 2 1 2 - 3 - 0 1 2 - - 2 - 1 2 3 - 2 1 2 2 3 3 2 1 0 1 - - 4 - 2 1 2 3 4 5 - 3 2 3 4 5

연구소의 상태가 주어졌을 때, 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구해보자.

입력

첫째 줄에 연구소의 크기 N(5 ≤ N ≤ 50), 놓을 수 있는 바이러스의 개수 M(1 ≤ M ≤ 10)이 주어진다.

둘째 줄부터 N개의 줄에 연구소의 상태가 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 2의 개수는 M보다 크거나 같고, 10보다 작거나 같은 자연수이다.

출력

연구소의 모든 빈 칸에 바이러스가 있게 되는 최소 시간을 출력한다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다.

*예제 입력 1 * 7 3 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 0 0 2

*예제 출력 1 * 5

*예제 입력 2 * 7 4 2 0 2 0 1 1 0 0 0 1 0 1 2 0 0 1 1 2 1 0 0 2 1 0 0 0 0 2 0 0 0 2 0 1 1 0 1 0 0 0 0 0 2 1 0 0 2 0 2

*예제 출력 2 * 4

* 바이러스 위치가 고정된 것이 아니라, 바이러스를 놓을 수 있는 자리를 알려줌, 바이러스가 놓기 전 자리는 빈칸과 같은 취급

* 모든 빈칸에 바이러스가 놓아지는 최소 시간

풀이

1. 입력받을 때** 바이러스 존이면 list에 넣기**, 바이러스를 놓을 수 있는 자리 확인하는 check 배열 초기화
2. DFS에서 조합을 활용해서 nCr
3. 1 내려가면서 check 배열에 1과 0넣어가면서 M까지 내려가기
4. 2 바이러스 갯수가 M에 도달했을 때, 이제 BFS 호출해 바이러스 확산 확인하기
5. BFS로 바이러스 확산 확인
6. 1. 현재 위치 배열에 영향을 끼치지 않게 깊은 배열 복사로, 복사 배열을 형성한다.
7. 2. 바이러스 넣은 곳 큐에 넣고, 방문(visted)배열 체크
8. 3. 사방돌면서 복사배열이 빈칸(0)이거나, 바이러스를 넣을 수 있는 자리(2)이고, 방문을 안했으면 => 시간증가, 큐에 넣기, 복사위치배열 바이러스 감염체크(3으로 수정), 방문배열 체크
9. BFS 끝난 후 배열돌면서, 빈칸(0)이거나, 바이러스를 넣을 수 있는 자리(2)가 남아 있으면 return(확산x), 아니면 시간 배열 중 최댓값구하기
10. 시간배열 최댓값들 중에서 최솟값 구하기

• check배열 - 바이러스를 놓은 자리, visited - 바이러스를 실제 넣고, 감염된 자리

public class Search_17141 {
    public static int N, M;
    public static int[][] arr;
    public static ArrayList<Point> list;
    public static int[] check; // 바이러스를 놓을 수 있는 자리
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };
    public static int minTime = Integer.MAX_VALUE;

    public static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    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());

        arr = new int[N][N];
        list = new ArrayList<Point>();

        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());

                // 바이러스를 놓을 수 있는 지리면 list에 넣기
                if(arr[i][j]==2) list.add(new Point(i,j));
            }
        }
        // 바이러스를 놓을 수 있는 자리 확인 
        check = new int[list.size()];

        DFS(0, 0);

        if(minTime==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(minTime);

    }

    public static void DFS(int start, int cnt) {
        //먼저 바이러스를 놓을 수 있는 k개의 위치 중 m개의 위치를 선정해야 한다. 이는 조합으로 나타낼 수 있다.
        if(cnt==M) {
            BFS(); //바이러스 확산 검사
            return;
        }
            // DFS에서 조합을 활용해서 nCr, 내려가면서 check 배열에 1과 0넣어가면서 M까지 내려가기
            for(int i=start; i<list.size(); i++) {
                check[i] = 1; //바이러스 설치
                DFS(i + 1, cnt+1);
                check[i] = 0; //바이러스 미설치
            }
        }
    }

    public static void BFS() {
        // 깊은 복사
        int[][] copy_arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            copy_arr[i] = arr[i].clone();
        }
        // 바이러스를 놓을 수 있는 자리들 중에 실제로 바이러스를 넣을 위치 선정
        for(int i=0; i<list.size(); i++) {
            if(check[i]==1) {
                Point po = list.get(i);
                // 바이러스 넣기
                copy_arr[po.x][po.y]=3;
            }
        }
        int[][] time = new int[N][N]; // 각 칸에 바이러스 퍼지기 위한 시간 계산
        int[][] visited = new int[N][N]; // 각 칸에 바이러스가 점염됬는지 여부 파악
        Queue<Point> que = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(copy_arr[i][j]==3) { // 실제 바이러스 있는자리
                    que.offer(new Point(i,j));
                    visited[i][j]=1; //확산
                }
            }
        }
        while(!que.isEmpty()) {
            Point now = que.poll();
            int x = now.x; 
            int y = now.y; 

            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if(0<=nx && nx<N && 0<=ny && ny<N) {
                    // 벽이 아니거나, 아직 바이러스가 확산되지 않은 장소
                    if((copy_arr[nx][ny] == 0||copy_arr[nx][ny] == 2) && visited[nx][ny]==0) {
                        time[nx][ny] = time[x][y]+1; // 다음 위치는 현재 위치에서 한번더 이동해야 한다.
                        if(time[nx][ny]>minTime) return; //현재 최소 시간보다 큰 곳은 굳이 방문할 필요 없다 - 시간절약
                        que.offer(new Point(nx,ny));
                        copy_arr[nx][ny] = 3; //실제 바이러스 점염
                        visited[nx][ny]=1; // 바이러스 점염

                    }
                }
            }
        }

        int maxtime =0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(copy_arr[i][j]==2||copy_arr[i][j]==0) {
                // 아직 바이러스가 확산되지 못한 곳이 있으면 확산 실패
                    return;
                }
                // 가장 값이 높은 곳이 바이러스가 마지막에 확신된 시간이다.
                maxtime = Math.max(maxtime, time[i][j]);
            }
        }
        minTime = Math.min(maxtime, minTime);

    }


}

* DFS로 경우의 수 찾고, BFS 확산에 사용

* 초기 여러 곳의 값을 저장할 때 리스트 사용

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

바이러스의 자리가 정해져있고, 안전영역의 크기를 구한다.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

*예제 입력 1 * 7 7 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0

*예제 출력 1 * 27

*예제 입력 2 * 4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2

*예제 출력 2 * 9

풀이

1. DFS로 위치에 벽을 넣고, 빼면서 내려가기
2. 1 DFS의 벽 갯수가 3이되면 BFS 계산 후 리턴
3. BFS로 바이러스 확산시키기
4. 1. 각 DFS의 경우의 수마다 바이러스 확산이 달라 기본 배열에 영향을 주지 않게 복사배열 마련
5. 2. 연구소 범위 밖이 아니고 빈칸일 경우에만 바이러스를 퍼트린다. (빈칸 -> 바이러스)
6. 만약 BFS로 확산 후에 배열에 0이 있으면 안전영역 갯수 증가, 최댓값 갱신하기

public class Search_14502 {
    public static int N, M;
    public static int[][] arr;
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };

    // 안전영역 최댓값 구하기
    public static int maxSafeZone = 0;

    public static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    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());

        arr = new int[N][M];

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

        DFS(0);

    /*
      // 결과확인
      for (int i = 0; i < N; i++) {
          for (int j = 0; j < M; j++) {
              System.out.print(arr[i][j]+" ");
          }
          System.out.println();
      }
    */

        System.out.println(maxSafeZone);

    }

    public static void DFS(int cnt) {
        if(cnt==3) { // 벽을 3개 다 설치 했다면
            BFS(); // 바이러스 확산시작
            return;
        }else {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(arr[i][j]==0) {
                        arr[i][j]=1; // 벽 넣었을 때
                        DFS(cnt+1); // 벽 갯수 증가
                        arr[i][j]=0; // 벽 넣지 않았을 때
                    }
                }
            }
        }
    }

    public static void BFS() {
        // 각 DFS의 경우의 수마다 바이러스 확산이 달라 기본 배열에 영향을 주지 않게 복사배열 마련
        // 깊은 복사
        int[][] copy_arr = new int[N][M];
        for (int i = 0; i < N; i++) {
            copy_arr[i] = arr[i].clone();
        }

        Queue<Point> que = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 바이러스 큐에 넣기
                if(copy_arr[i][j]==2) {
                    que.offer(new Point(i,j));
                }
            }
        }

        while(!que.isEmpty()) {
            Point now = que.poll();
            int x = now.x; // 현재 값
            int y = now.y; //

            // 바이러스 사방 확산
            for(int k=0; k<4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                //연구소 범위 밖이 아니고 빈칸일 경우에만 바이러스를 퍼트린다.
                if(0<=nx && nx<N && 0<=ny && ny<M) {
                    if(copy_arr[nx][ny] == 0) {
                        que.offer(new Point(nx,ny)); 
                        // 바이러스 점령
                        copy_arr[nx][ny] = 2;
                    }
                }
            }
        }

        // 바이러스 확인 후 안전영역 확인
        int safeZone =0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(copy_arr[i][j]==0) {
                    safeZone++;
                }
            }
        }
        // 안전영역 최댓값 구하기
        if(safeZone>maxSafeZone) maxSafeZone=safeZone;
    }


}

* DFS로 경우에 수 다 구하고, 끝에서 BFS로 확산 검사하기

* 배열을 복사할 떄 얕은 주소값만 복사하는 게 아닌 완전 깊은 복사를 해야 기존 배열에 영향을 주지 않는다.

13913. 숨바꼭질4 (골드4)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

12851) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

13913) 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

12851) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다. 13913) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

*12851. 예제 입력 * 5 17

*12851. 예제 출력 * 4 2

*13913. 예제 입력 * 5 17

13913. 예제 출력 (스페셜 저지) 4 5 10 9 18 17

13913. 예제 출력 (스페셜 저지) 4 5 4 8 16 17

풀이

코드

1. 동생을 찾는 가장 빠른 방법을 찾기 위해 parent 배열 선언
2. 수빈이 더 뒤쪽에 있으면 후퇴하는 방법 밖에 없다. -1씩 후퇴하기
3. BFS 호출, 반복문 돌면서 -1, 1, 2 더해가면서 next 구하기
4. 1. 범위 내에 있고 동생을 만나면 cnt 증가 (12851), 최소시간 갱신
5. 최소시간이 0이거나, 갱신시간==이전시간+1 일 때 큐에 넣거나, 시간 갱신
6. 1. 다음 위치의 이전 위치는 현재 위치이다.
7. 도착점 위치를 처음으로 parent 배열의 값을 stack에 넣고, 마지막에 빼면서 출력 => 경로출력

• 12851의 응용버전인 13913을 기준으로 코드를 작성한다.

  public class Search_13913 {
    public static int N, K;
    public static int[] parent = new int[100001]; // 동생을 찾는 가장 빠른 방법을 찾기 위해 사용
    public static int[] time = new int[100001]; // 동생을 찾는 가장 빠른 시간을 찾기 위해 사용
    public static int minTime; // 가장 빠른 시간
    //public static int cnt; - 12851 가장 빠른 시간으로 찾는 방법의 갯수
  
    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()); // 남동생
  
        //수빈이 더 뒷쪽에 있으면 후퇴하는 방법 밖에 없다. -1씩 후퇴하기
        if (N >= K) {
            System.out.println(N - K); //minTime
            for(int i=N;  i>K; i--) {
                System.out.print(i+" ");
            }
            System.out.println(K);
            return;
        }
  
        //cnt = 0; - 12851
        minTime = Integer.MAX_VALUE;
  
        BFS();
        System.out.println(minTime);
        //System.out.println(cnt); - 12851
  
  

    // 도착점에서 츨발점까지 거슬러 올라가기
    Stack<Integer> stk = new Stack<Integer>();
    stk.push(K);
    int idx = K;

    while(idx!=N) {
        stk.push(parent[idx]);
        idx = parent[idx];
    }

    // 스택으로 거꾸로 경로출력
    while(!stk.isEmpty()) {
        System.out.print(stk.pop()+" ");
    }

    System.out.println();

}

public static void BFS() {
    Queue<Integer> que = new LinkedList<Integer>();

    // 시작위치 설정
    que.offer(N);
    time[N] = 1;

    while (!que.isEmpty()) {
        int now = que.poll();
        if (minTime < time[now])
            return;

        for (int i = 0; i < 3; i++) {
            int next = now; // * 시작점에서 다른걸 시도할 때마다, 다시 시작점으로 와야한다.
            if (i == 0) {
                next -= 1;
            } else if (i == 1) {
                next += 1;
            } else {
                next *= 2;
            }

            if (next < 0 || next > 100000)
                continue;

            if (next == K) { // 동생 만남
                minTime = time[now];
                //cnt++; - 12851
            }

            //time[next] > time[now] + 1 => 가능하긴 하지만 경우가 많아서 메모리초과
            if (time[next] == 0 || time[next] == time[now] + 1) {
                que.offer(next);
                time[next] = time[now] + 1; // 걸리는 시간 갱신
                parent[next] = now; // 다음 위치의 이전 위치는 현재 위치이다.
            }
        }

    }
}

}

```

* BFS 사용

* 가는 방법이 하나 밖에 없을 때 (뒤로가기), 그 방법 먼저 계산

* 도착지 점에서부터 출발점 경로 찾가 => parent[next]=now, 스택사용

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

13459) 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

13460) 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

15653) 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

13459) 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력한다. 13460) 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다. 15653) 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 어떻게 움직여도 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

*13459. 예제 입력 1 * 7 7 ####### #..R#B# #.##### #.....# #####.# #O....# #######

*13459. 예제 출력 1 * 1

*13459. 예제 입력 2 * 10 10 ########## #R#...##B# #...#.##.# #####.##.# #......#.# #.######.# #.#....#.# #.#.#.#..# #...#.O#.# ##########

*13459. 예제 출력 2 * 0

*13460/15653. 예제 입력 1 * 10 10 ########## #R#...##B# #...#.##.# #####.##.# #......#.# #.######.# #.#....#.# #.#.##...# #O..#....# ##########

*13460/15653. 예제 출력 1 * 7

*13460/15653. 예제 입력 2 * 3 10 ########## #.O....RB# ##########

*13460/15653. 예제 출력 2 * -1

풀이

1. 좌표이동 배열, Point 클래스 (빨간공과 파란공의 x,y축) 마련
2. 배열 입력받을 때 빨간공, 파란공의 시작위치 확인해서 BFS 메소드에 매개변수로 전달
3. 빨간공과 파란공의 시작위치를 큐에 넣고, 시작위치를 방문배열에 체크
4. 시도횟수 만큼 반복문 돌기 / 시작점 마다 반복문 돌기 (que.size) / 시작점에서 방향 확인해 다음 위치 파악하기 => 3중 반복문
5. 방향에 따라 빨간공과 파란공의 어떤게 앞서서 이동하나 확인하고 함수 호출
6. 1. 같은 y축에 있고 && (방향이 북쪽이고 파란공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 파란공에 더 아래쪽에 있을 때) => 파란색 공이 더 앞서서 이동
7. 2. 같은 y축에 있고 && (방향이 북쪽이고 빨간공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 빨간공에 더 아래쪽에 있을 때) => 빨간색 공이 더 앞서서 이동
8. 3. 같은 x축에 있고 && (방향이 서쪽이고 파란공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 파란공에 더 오른쪽에 있을 때) => 파란색 공이 더 앞서서 이동
9. 4. 같은 x축에 있고 && (방향이 서쪽이고 빨간공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 빨간공이 더 오른쪽에 있을 때) => 빨간공이 더 앞서서 이동
10. 5. 둘이 x축 y축 서로 다르면 어떤 공이 먼저 움직이든 상관없다. (방향이 북,남이면 y축 고정, x축 이동 / 방향이 서,동이면 x축 고정, y축 이동)
11. 빨간공, 파란공이 이동함수를 호출 후
12. 1. 방문했거나, 파란공이 먼저 빠지면 넘어감
13. 2. 빨간공이 빠지면 최소횟수 계산 후 리턴
14. 3. 위의 조건아니면 다음 점을 큐에 넣고, 방문배열 체크
15. 시도횟수 증가
16. 이동함수는 방향을 매개변수로 받아 방향배열을 사용하여 지정된 방향으로 이동
17. 1. 벽이 아닐 때까지 이동하고 구멍에 빠지면 현재 시점 리턴
18. 2. 벽에 도달하거나 다른 공과 만나면 현재 시점보다 하나 후퇴한 점 리턴

코드

13459 기준으로 코드를 작성하고 13460과 15653은 주석으로 적어놓았다.

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

public class Main {
    public static int N, M;
    public static char[][] arr;
    /*
     최솟값을 찾기위해 초기값은 가장 큰 값으로 지정- 13460, 15653
     public static int answer = Integer.MAX_VALUE; 
    */

    // 북(0), 남(1), 서(2), 동(3) 
    public static int[] dx = { -1, 1, 0, 0 };
    public static int[] dy = { 0, 0, -1, 1 };

    public static class Point { //빨간공, 파란공 위치
        int red_x;
        int red_y;
        int blue_x;
        int blue_y;

        public Point(int red_x, int red_y, int blue_x, int blue_y) {
            this.red_x = red_x;
            this.red_y = red_y;
            this.blue_x = blue_x;
            this.blue_y = blue_y;
        }
    }

    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());
        arr = new char[N][M];

        // 빨간, 파란공 시작 위치 저장
        int redR = 0;
        int redC = 0;
        int blueR = 0;
        int blueC = 0;

        // 입력받으면서 빨간공과 파란공의 시작 위치 파악
        for (int r = 0; r < N; r++) {
            String input = br.readLine();
            for (int c = 0; c < M; c++) {
                arr[r][c] = input.charAt(c);
                if (arr[r][c] == 'R') {
                    redR = r;
                    redC = c;
                } else if (arr[r][c] == 'B') {
                    blueR = r;
                    blueC = c;
                }
            }

        }

        BFS(redR, redC, blueR, blueC);
        System.out.println(answer); // 최소시도횟수 출력 - 13460, 15653
    }

    public static void BFS(int rx, int ry, int bx, int by) {
        Queue<Point> queue = new LinkedList<>();
        //공의 시작위치 받아서 큐에 넣기
        queue.offer(new Point(rx, ry, bx, by));
        boolean[][][][] visited = new boolean[N][M][N][M]; // 방문 4차원 배열
        visited[rx][ry][bx][by] = true; // 시작위치 방문
        int cnt = 1; // 처음시도 ( cnt=0을 하려면 밑에 반복문에서 cnt<10해야함)

        while (!queue.isEmpty() && cnt <= 10) { // 10의 시도
        // while (!queue.isEmpty()) { //15653. 횟수제한 없음

            int size = queue.size();

            // 다른 시작점의 경우의 수를 모두 검사
            for (int s = 0; s < size; s++) {
                Point current = queue.poll();
                // System.out.println("현재 위치 : "+current.red_x+" "+current.red_y+" "+current.blue_x+" "+current.blue_y);

                for (int d = 0; d < 4; d++) {
                    // 다음 공의 위치
                    int nrx = current.red_x;
                    int nry = current.red_y;
                    int nbx = current.blue_x;
                    int nby = current.blue_y;

                    /*
                    boolean redfirst = false;
                    if(d==0 && nrx < nbx) redfirst = true; //북
                    if(d==1 && nrx > nbx) redfirst = true; //남
                    if(d==2 && nry < nby) redfirst = true; //서
                    if(d==3 && nry > nby) redfirst = true; //동
                    => 사용안하는 이유: 위에서 하나를 만족해서 redfirst가 true됬다고 해서 밑에서 방향과 좌표가 맞다고 단정할 수 없음 
                     */

                    // 빨간광과 파란공의 이동방향에 따라 선후관계 파악하기
                    if (nby == nry && ((d == 0 && nbx < nrx) || (d == 1 && nbx > nrx))) {
                    // 같은 y축에 있고  && (방향이 북쪽이고 파란공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 파란공에 더 아래쪽에 있을 때)
                    // 파란색 공이 더 앞서서 이동
                        nbx = slideX(nbx, nby, nrx, nry, d);
                        nrx = slideX(nrx, nry, nbx, nby, d);
                    } else if (nby == nry && (((d == 0 && nbx > nrx) || d == 1 && nbx < nrx))) {
                    // 같은 y축에 있고  && (방향이 북쪽이고 빨간공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 빨간공에 더 아래쪽에 있을 때)
                    // 빨간색 공이 더 앞서서 이동
                        nrx = slideX(nrx, nry, nbx, nby, d);
                        nbx = slideX(nbx, nby, nrx, nry, d);
                    } else if (nbx == nrx && ((d == 2 && nby < nry) || (d == 3 && nby > nry))) {
                    // 같은 x축에 있고  && (방향이 서쪽이고 파란공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 파란공에 더 오른쪽에 있을 때)
                    // 파란색 공이 더 앞서서 이동
                        nby = slideY(nbx, nby, nrx, nry, d);
                        nry = slideY(nrx, nry, nbx, nby, d);
                    } else if (nbx == nrx && ((d == 2 && nby > nry) || (d == 3 && nby < nry))) {
                     // 같은 x축에 있고  && (방향이 서쪽이고 빨간공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 빨간공이 더 오른쪽에 있을 때)
                    // 빨간공이 더 앞서서 이동
                        nry = slideY(nrx, nry, nbx, nby, d);
                        nby = slideY(nbx, nby, nrx, nry, d);

                    } else {
                        // 둘이 x축 y축 서로 다르면 어떤 공이 먼저 움직이든 상관없다.
                        /*
                         위에 조건문을 nbx == nrx 와 nby == nry로 먼저 묶지 않는 이유는 else문 처리 때문이다.
                         &&문 만족하지 않으면 다 else로 넘어온다. => &&로 묶으면 else로 넘어오는 케이스가 많아진다.
                         */
                        if (d == 0 || d == 1) { 
                            // 방향이 북,남이면 y축 고정, x축 이동
                            nbx = slideX(nbx, nby, nrx, nry, d);
                            nrx = slideX(nrx, nry, nbx, nby, d);
                        } else {
                            // 방향이 서,동이면 x축 고정, y축 이동
                            nby = slideY(nbx, nby, nrx, nry, d);
                            nry = slideY(nrx, nry, nbx, nby, d);
                        }
                    }

                    // System.out.println("다음 위치 : "+nrx+" "+nry+" // "+nbx+" "+nby);

                    // 방문했거나, 파란공이 먼저 빠지면 넘어감
                    if (visited[nrx][nry][nbx][nby] || (arr[nbx][nby] == 'O'))
                        continue;
                    // 빨간공이 빠지면 리턴
                    if (arr[nrx][nry] == 'O') {
                        /*
                            13460, 15653 - 바로 출력하지 않고 최솟값 계산
                            answer = Math.min(cnt, answer)
                        */
                        System.out.println("1");
                        return;
                    }
                    // System.out.println("다음 위치 안넘어감 : "+nrx+" "+nry+" // "+nbx+" "+nby);
                    queue.offer(new Point(nrx, nry, nbx, nby));
                    visited[nrx][nry][nbx][nby] = true;
                }
            }

            // 맨 끝에 시도횟수 증가
            cnt++;
        } // while문의 끝 - 밑은 시도했지만 불가능함



        /*
            13460, 15653 - 탈출 불가능 할 때 -1 출력
            System.out.println(-1);
            System.exit(0);
        */
        System.out.println(0);
    }

    public static int slideX(int currentR, int currentC, int diffR, int diffC, int d) {

        while (arr[currentR][currentC] != '#') { //벽이 아닐 때까지 이동
            currentR = currentR + dx[d];

            if (arr[currentR][currentC] == 'O') { // 구멍에 빠짐
                return currentR;
            }

            if (currentR == diffR && currentC == diffC) { //다른 공에 도착하면 하나 뒤로 가기
                return currentR - dx[d];
            }

        }

        //벽에 도달하면 하나 뒤로가기
        return currentR - dx[d];
    }

    public static int slideY(int currentR, int currentC, int diffR, int diffC, int d) {

        while (arr[currentR][currentC] != '#') { //벽이 아닐 때까지 이동
            currentC = currentC + dy[d];

            if (arr[currentR][currentC] == 'O') { // 구멍에 빠짐
                return currentC;
            }

            if (currentR == diffR && currentC == diffC) { //다른 공에 도착하면 하나 뒤로 가기
                return currentC - dy[d];
            }

        }

        //벽에 도달하면 하나 뒤로가기
        return currentC - dy[d];

    }

}

* BFS 사용

* 시도 횟수, 시간에 따른 큰 반복문 실행, 그 안에서 각 시작점에 대한 반복문 실행 (que.size())

* 방향에 따라 x축, y축의 이동 변화 / 선후순서 확인

문제

당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다.

당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마나 걸릴까?

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 세 개의 정수 L, R, C로 시작한다. L(1 ≤ L ≤ 30)은 상범 빌딩의 층 수이다. R(1 ≤ R ≤ 30)과 C(1 ≤ C ≤ 30)는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.

그 다음 각 줄이 C개의 문자로 이루어진 R개의 행이 L번 주어진다. 각 문자는 상범 빌딩의 한 칸을 나타낸다. 금으로 막혀있어 지나갈 수 없는 칸은 '#'으로 표현되고, 비어있는 칸은 '.'으로 표현된다. 당신의 시작 지점은 'S'로 표현되고, 탈출할 수 있는 출구는 'E'로 표현된다. 각 층 사이에는 빈 줄이 있으며, 입력의 끝은 L, R, C가 모두 0으로 표현된다. 시작 지점과 출구는 항상 하나만 있다.

출력

각 빌딩에 대해 한 줄씩 답을 출력한다. 만약 당신이 탈출할 수 있다면 다음과 같이 출력한다. Escaped in x minute(s). 여기서 x는 상범 빌딩을 탈출하는 데에 필요한 최단 시간이다. 만일 탈출이 불가능하다면, 다음과 같이 출력한다. Trapped!

*예제 입력 1 * 3 4 5 S.... .###. .##.. ###.#

##### ##### ##.## ##...

##### ##### #.### ####E

1 3 3 S## #E# ###

0 0 0

*예제 출력 1 * Escaped in 11 minute(s). Trapped!

풀이

1. 상하좌우 위아래 3개의 위치좌표, 삼중배열 => arr, dis (도착할 때까지 거리계산하는 배열)
2. 시작점부터 시작해서 BFS 돌아서 도착점에 도달
3. dis[다음 도달 위치] = dis[현재위치] + 1

public class Search_6593 {
    public static int L,R,C;
    public static String[][][] arr; // 위치배열
    public static int[][][] dis; // 거리배열
    public static int[] dx = {-1,0,1,0,0,0}; // x축 이동
    public static int[] dy = {0,-1,0,1,0,0}; // y축 이동
    public static int[] dz = {0,0,0,0,1,-1}; // 위, 아래 배열
    static class Point{ 
        int l; // 층
        int r; // x축
        int c; // y축

        public Point(int l, int r, int c) {
            this.l = l;
            this.r = r;
            this.c = c;
        }
    }
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        while(true) {
            st = new StringTokenizer(br.readLine());
            //L은 상범 빌딩의 층 수이다. R과 C는 상범 빌딩의 한 층의 행과 열의 개수를 나타낸다.
            L = Integer.parseInt(st.nextToken());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            if(L==0 && R==0 && C==0) break; // 모두 0이면 입력 중지

            arr = new String[L][R][C];
            dis = new int[L][R][C];

            // 시작 위치
            int sL = 0;
            int sR = 0;
            int sC = 0;

            // 도착 위치
            int eL = 0;
            int eR = 0;
            int eC = 0;

            for(int t=0; t<L; t++) {
                for (int i = 0; i < R; i++) {
                    String str = br.readLine();
                    String[] sta = str.split("");
                    for (int j = 0; j < C; j++) {
                        arr[t][i][j] = sta[j];
                        if(arr[t][i][j].equals("S")){
                            sL =t; sR = i; sC = j;
                        }else if(arr[t][i][j].equals("E")){
                            eL =t; eR = i; eC = j;
                        }
                    }
                }
                String space = br.readLine();
            } 
            BFS(sL,sR,sC);

//            System.out.println(dis[eL][eR][eC]);
//            
//            for(int t=0; t<L; t++) {
//                for(int i = 0; i < R; i++) {
//                    for (int j = 0; j < C; j++) {
//                        System.out.print(dis[t][i][j]);
//                    }
//                    System.out.println();
//                }
//                System.out.println("--------------------------");
//            }

            // 도착 못했음
            if(dis[eL][eR][eC]==0) {
                System.out.println("Trapped!");
            }else { //도착
                System.out.println("Escaped in "+dis[eL][eR][eC]+" minute(s).");
            }
        }


    }

    public static void BFS(int sl, int sr, int sc) {
        Queue<Point> que = new LinkedList<Point>();
        que.offer(new Point(sl,sr,sc));

        while(!que.isEmpty()) {
            Point po = que.poll();
            for(int i=0; i<6; i++) {
                int nl = po.l + dz[i];
                int nr = po.r + dx[i];
                int nc = po.c + dy[i];
                if(nl<0 || nr<0 || nc<0 || nl>=L || nr >=R || nc >=C) continue;

                // 벽이거나 이미 왔던 곳이면 넘어가기
                if(arr[nl][nr][nc].equals("#") || dis[nl][nr][nc]!=0) continue;

                que.offer(new Point(nl,nr,nc));

                // 다음위치는 현재위치에서 한번 더 이동한 곳임
                //dis[다음 도달 위치] = dis[현재위치] + 1
                dis[nl][nr][nc] = dis[po.l][po.r][po.c]+1;
            }
        }
    }
}

* BFS

* 3차원 배열 이동

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

*예제 입력 1 * 9 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 0 0 0 1 1 1 -1 -1 -1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 -1 0 1 -1 0 1 -1 0 -1 1 0 1 -1 0 1 -1 0 1 -1 1 0 -1 0 1 -1

*예제 출력 1 * 10 12 11

풀이

1. DFS 내려가면서 size 1/3으로 줄이기
2. 위치 , 위치 + size, 위치 + (2*size)
3. 정사각형의 수가 모두 일치하는지 확인한다 => check 배열

public class Search_1780 {
    public static int N;
    public static int[][] arr;
    public static int black =0; //-1
    public static int grey = 0; // 0
    public static int white = 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());

        arr = new int[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());
            }
        }

        DFS(0, 0, N);

        System.out.println(black);
        System.out.println(grey);
        System.out.println(white);


    }
    public static void DFS(int row, int col, int size) {
        if(isCheck(row, col, size)) {
            int color = arr[row][col];
            if(color==-1) {
                black++;
            }else if(color==0) {
                grey++;
            }else {
                white++;
            }
        }else {
            // DFS 내려가면서 size 1/3으로 줄이기
            int new_size = size/3;

            // 가로, 세로로 시작 위치 조절
            DFS(row, col, new_size);
            DFS(row, col+new_size, new_size);
            DFS(row, col+2*new_size, new_size);

            DFS(row+new_size, col, new_size);
            DFS(row+new_size, col+new_size, new_size);
            DFS(row+new_size, col+2*new_size, new_size);

            DFS(row+2*new_size, col, new_size);
            DFS(row+2*new_size, col+new_size, new_size);
            DFS(row+2*new_size, col+2*new_size, new_size);
        }

    }
    // 정사각형으로 같은 색인지 확인
    public static boolean isCheck(int row, int col, int size) {
        int color = arr[row][col];
        for(int i=row; i<row+size; i++) {
            for(int j=col; j<col+size; j++) {
                if(arr[i][j]!=color) return false;
            }
        }
        return true;
    }
}

* DFS

* 분할 정복 : size 1/3으로 줄여가면서 내려가기 => 위치 , 위치 + size, 위치 + (2*size)

문제

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤던 칸을 다시 거쳐도 되며, 0으로 시작하는 000123과 같은 수로 만들 수 있다.

숫자판이 주어졌을 때, 만들 수 있는 서로 다른 여섯 자리의 수들의 개수를 구하는 프로그램을 작성하시오.

입력

다섯 개의 줄에 다섯 개의 정수로 숫자판이 주어진다.

출력

첫째 줄에 만들 수 있는 수들의 개수를 출력한다.

*예제 입력 1 * 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1

*예제 출력 1 * 15

힌트 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다.

풀이

1. DFS로 내려가면서 문자열 추가, cnt 증가
2. cnt가 6이 됬을 때, hashset에 넣어 중복 제거

import codingTest.Search_2468.Point;
public class Search_2210 {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = 5;

        arr = new int[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());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                DFS(i,j,"",0);
            }
        }
        System.out.println(hash.size());
    }
    public static void DFS(int row, int col, String sb, int cnt) {
        if(cnt==6) { //문자열의 갯수가 6이 되었을 때 
            //System.out.println(sb);

            //hashset에 넣어 중복제거
            hash.add(sb);
        }else {
            for(int w=0; w<4; w++) {
                // 사방을 돌아서 수 찾기
                int xx = row + dx[w];
                int yy = col + dy[w];

                if(xx<0 || xx>=N || yy<0 || yy>=N ) continue;
                // 이동한 위치의 x축, 이동한 위치의 y축, 문자열 추가, 문자 갯수 추가
                DFS(xx,yy,sb+arr[xx][yy],cnt+1);
            }
        }
    }
}

* DFS

* 중복을 없애기 위해 Hastset 사용

문제

사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를 연결해야 한다. 사다리 게임은 각각의 세로선마다 게임을 진행하고, 세로선의 가장 위에서부터 아래 방향으로 내려가야 한다. 이때, 가로선을 만나면 가로선을 이용해 옆 세로선으로 이동한 다음, 이동한 세로선에서 아래 방향으로 이동해야 한다. 위의 그림에서 1번은 3번으로, 2번은 2번으로, 3번은 5번으로, 4번은 1번으로, 5번은 4번으로 도착하게 된다. 아래 두 그림은 1번과 2번이 어떻게 이동했는지 나타내는 그림이다. 사다리에 가로선을 추가해서, 사다리 게임의 결과를 조작하려고 한다. 이때, i번 세로선의 결과가 i번이 나와야 한다. 그렇게 하기 위해서 추가해야 하는 가로선 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세로선의 개수 N, 가로선의 개수 M, 세로선마다 가로선을 놓을 수 있는 위치의 개수 H가 주어진다. (2 ≤ N ≤ 10, 1 ≤ H ≤ 30, 0 ≤ M ≤ (N-1)×H) 둘째 줄부터 M개의 줄에는 가로선의 정보가 한 줄에 하나씩 주어진다. 가로선의 정보는 두 정수 a과 b로 나타낸다. (1 ≤ a ≤ H, 1 ≤ b ≤ N-1) b번 세로선과 b+1번 세로선을 a번 점선 위치에서 연결했다는 의미이다. 가장 위에 있는 점선의 번호는 1번이고, 아래로 내려갈 때마다 1이 증가한다. 세로선은 가장 왼쪽에 있는 것의 번호가 1번이고, 오른쪽으로 갈 때마다 1이 증가한다. 입력으로 주어지는 가로선이 서로 연속하는 경우는 없다.

출력

i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다.

*예제 입력 1 * 5 5 6 1 1 3 2 2 3 5 1 5 4

*예제 출력 1 * 3

*예제 입력 2 * 2 0 3

*예제 출력 2 * 0

*예제 입력 3 * 2 1 3 1 1

*예제 출력 3 * 1

풀이

1. main

2. 1 사다리타기가 진행중인지, 끝인지 파악하기 위해 finish 변수 선언

3. 2. 입력받을 때, 받은 좌표의 오른쪽으로는 1, 왼쪽으로는 2표시 (왼쪽은 세로 좌표 -1)
4. 3. 추가할 수 있는 사다리 3개 => 3번의 반복문 DFS 내려가서 finish가 true로 변하면 수를 출력한다. 3번을 초과하면 더 이상 사다리를 추가할 수 없다 => -1 출력

5. DFS 함수 (시작 가로 위치, 현재 사다리의 갯수, 최대 놓을 수 있는 사다리의 갯수)

6. 1. finish 변수가 true이면 더 이상 진행 x, return
7. 2. 현재 사다리의 개수가 max개 일 때, check 함수 호출해 확인하고, finish 변경
8. 3. for(시작 가로위치 ~ H) / for (1 ~ L)

9. 3.1 arr[r][c]와 왼쪽, 오른쪽이 0이 아니면 (사다리가 있으면) 설치 못하고 넘어가기

10. 3.2 설치 가능하면, arr[r][c]=1, arr[r][c-1]=2 설치하기

11. 3.3. DFS(시작 가로 위치+1, 현재 사다리의 갯수+1, 최대 놓을 수 있는 사다리의 갯수)

12. 3.4. arr[r][c]=0, arr[r][c-1]=0로 사다리 설치 제거하기

13. 체크함수

14. 1. 세로 확인하기 (나간게 다시 들어오나), 가로 한칸씩 내려가기
15. 2. 가로 내려가면서 배열값이 1이면 왼쪽으로 세로 이동, 2이면 오른쪽으로 세로이동
16. 3. 만약 세로 나간게 다시 돌아오지 않았다면 return false

public class Search_15684 {
    public static int L,M,H;
    public static int[][] arr;
    public static boolean finish;
    public static void main(String[] args) throws IOException{

             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            L = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            H = Integer.parseInt(st.nextToken());

            arr = new int[H+1][L+1]; 

            finish = false; // 사다리타기가 진행중인지, 끝인지 파악하기 위해 변수 선언

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                arr[r][c] = 1; // 오른쪽 가로 표시
                arr[r][c-1] = 2; // 왼쪽 가로 표시
            }

            for (int i = 0; i <= 3; i++) { //추가할 수 있는 사다리 3개
                DFS(1, 0, i);
                if(finish) { // DFS 내려가서 finish가 true로 변하면 수를 출력한다. 
                    System.out.println(i);
                    System.exit(0);
                }
            }
            // 3번을 초과하면 더 이상 사다리를 추가할 수 없다
            System.out.println(-1);

        }

    //DFS(1, 0, i); => (시작 가로 위치, 현재 사다리의 갯수,최대 놓을 수 있는 사다리의 갯수)
    //nr이 없고 가로가 1부터 시작해도 된다. 하지만 시간이 늘어난다. => 높이가 내려가면서 사다리를 추가한다.
    public static void DFS(int nr, int cnt, int size) {
        if(finish) return;
            if (cnt == size) {
                if (check()) {
                    finish = true;
                }
                return;
            }

            for (int r = nr; r <= H; r++) { //가로
                for (int c = 1; c < L; c++) {//세로
                    if (arr[r][c] == 1) // 가로선은 서로 접하면 안 된다
                        continue;
                    if (arr[r][c - 1] == 1) { //두 가로선이 연속하면 안된다, 왼쪽에 이미 있으면 놓을 수 없븜
                        continue;
                    }
                    if (arr[r][c + 1] == 1) { //두 가로선이 연속하면 안된다, 오른쪽에 이미 있으면 놓을 수 없음
                        continue;
                    }
                    arr[r][c] = 1; //오른쪽 
                    arr[r][c-1]=2; //왼쪽
                    DFS(r, cnt + 1, size);
                    arr[r][c] = 0;
                    arr[r][c-1]=0;
                }
            }
        }

    public static boolean check() {
            for (int i = 1; i <= L; i++) {
                int now = i; //세로 사타리 타가면서 검사 나간게 다시 들어오나 검사
                int start = 1; //가로 내려 가면서 검사
                while (start <= H) {
                    if (arr[start][now] == 1) {
                        now--;
                    } else if (arr[start][now] == 2) {
                        now++; 
                    }
                    start++; //가로 칸 내려가기
                }
                if (i != now) //나간게 다시 들어오지 않으면 false
                    return false;
            }
            return true;
        }

    public static void print() {
            for(int i=0; i<=H; i++) {
                for(int j=0; j<=L; j++) {
                    System.out.print(arr[i][j]+" ");
                }
                System.out.println();
            }
        }
}

* DFS, 순열조합

* 가로선이 연속하거나 서로 접하면 안 된다 => 한 점을 기준으로 오른쪽(1), 왼쪽(2)의 구분

* 세로선의 이동 => 왼쪽 이동 시 세로--, 오른쪽 이동 시 세로++

문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다).

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

*예제 입력 1 * 5 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7

*예제 출력 1 * 5

*예제 입력 2 * 7 9 9 9 9 9 9 9 9 2 1 2 1 2 9 9 1 8 7 8 1 9 9 2 7 9 7 2 9 9 1 8 7 8 1 9 9 2 1 2 1 2 9 9 9 9 9 9 9 9

*예제 출력 2 * 6

풀이

1. 배열을 입력받을 때 최고높이를 찾고, 반복문으로 0부터 최고 높이까지 물이 차는 경우를 계산
2. BFS 사용. 사방돌면서 범위에 맞고, 높이가 비보다 높은지, 방문했는지 확인한다.

public class Search_2468 {
    public static int N;
    public static int[][] arr;
    public static boolean[][] check;
    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    static class Point{
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    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());

        arr = new int[N][N];

        // 가장 최고 높이 구하기
        int max = 0;
        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());
                max = Math.max(max, arr[i][j]);
            }
        }

        // 안전 영역 최대 갯수
        int area_max = 0;

        // 0부터 최고 강수량 높이까지 계산
        for(int t=0; t<=max; t++) {
            check = new boolean[N][N];
            int area = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {

                    // 영역의 높이가 강수랭보다 높고, 방문을 안했던 영역일 때
                    if(arr[i][j]>t && check[i][j]==false) {
                        Queue<Point> que = new LinkedList<Point>();
                        que.offer(new Point(i,j));
                        check[i][j]=true;
                        area++;

                        // 사방 돌아 현재 지점과 이어진 안전영역이 있는지 확인
                        while(!que.isEmpty()) {

                            Point po = que.poll();
                            for(int w=0; w<4; w++) {
                                int xx = po.x +dx[w];
                                int yy = po.y +dy[w];

                                if(xx<0 || xx>=N || yy<0 || yy>=N ) {
                                    continue;
                                }
                                // 주변에 영역의 높이가 강수랭보다 높고, 방문을 안했던 영역일 때
                                if(arr[xx][yy]>t && check[xx][yy]==false) {
                                    que.offer(new Point(xx,yy));
                                    check[xx][yy]=true;
                                }
                            }
                        }
                    }
                }
            }

            // 안전영역 최대 갯수 계산
            area_max = Math.max(area_max, area);

//          각 강수량 마다 안전영역 갯수 확인 출력
//            System.out.println("==============물 깊이"+t);
//            for (int i = 0; i < N; i++) {
//                for (int j = 0; j < N; j++) {
//                    System.out.print(check[i][j]+" ");
//                }
//                System.out.println();
//            }
//            System.out.println("------------------------"+area);        
        }
        System.out.println(area_max);


    }
}

* BFS

* 처음부터 max값을 구해, 0부터 max값까지 차례로 시뮬레이션을 돌린다.

문제

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

*예제 입력 1 * 6 6 ..S... ..S.W. .S.... ..W... ...W.. ......

*예제 출력 1 * 1 ..SD.. ..SDW. .SD... .DW... DD.W.. ......

*예제 입력 2 * 1 2 SW

*예제 출력 2 * 0

풀이

1. 배열 돌면서 늑대(w)나오면 사방검사를 한다
2. 사방검사 해서 양(s)이 나오면 불가(0), 양이 아니면 울타리(D)를 친다.

public class Search_16956 {
    public static int R,C;
    public static String[][] arr; //위치 배열
    // 사방검사
    public static int[] dx = {-1, 0, 1, 0};
    public 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());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        arr = new String[R][C];

        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            String[] strArr = str.split("");
            for(int j = 0; j < C; j++) {
                arr[i][j] = strArr[j];
            }
        }

        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(arr[i][j].equals("W")) {
                    for(int t =0;t<4; t++) {
                        int xx = i + dx[t];
                        int yy = j + dy[t];
                        if(xx<0 || xx>R-1 || yy<0 || yy>C-1 ) continue;
                        //양이 나오면 진행 불가
                        if(arr[xx][yy].equals("S")) {
                            System.out.println("0");
                            System.exit(0);

                         // 양아 아닌 빈칸이 나오면 울타리를 친다.
                        }else if(arr[xx][yy].equals(".")) {
                            arr[xx][yy]="D";
                        }
                    }
                }
            }
        }

        // 양이 잡아 먹히지 않으면 성공(1) 찍고 배열 출력
        System.out.println("1");
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }

    }
}

* BFS 사용

문제

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다. (만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력

첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베이터로 이동할 수 없을 때는 "use the stairs"를 출력한다.

*예제 입력 1 * 10 1 10 2 1

*예제 출력 1 * 6

*예제 입력 2 * 100 2 1 1 0

*예제 출력 2 * use the stairs

풀이

1. 거리이동배열(dis), 체크배열, BFS 사용

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int F = Integer.parseInt(st.nextToken()); // 전체층
        int S = Integer.parseInt(st.nextToken()); // 시작
        int G = Integer.parseInt(st.nextToken()); //도착
        int U = Integer.parseInt(st.nextToken()); //up
        int D = Integer.parseInt(st.nextToken()); //down    

        int[] dis = new int[F+1]; //거리이동 배열 (1~F)층
        boolean[] check = new boolean[F+1]; //체크 배열 (1~F)층
        Queue<Integer> que = new LinkedList<Integer>();

        dis[S]=0; // 처음 시작점(s)의 이동거리는 0
        check[S]=true; // 처음 시작점(s) 방문했다.
        que.offer(S);

        int[] move = {U, -1*D}; //위, 아래만 이동 가능

        while(!que.isEmpty()) {
            int now = que.poll();

            if(now==G) { //도착하면 아동거리 출력 후 빠져나오기
                System.out.println(dis[G]);
                System.exit(0);
            }

            for(int i=0;i<2; i++) { //위, 아래 배열 반복하며 도달 층인지 확인
                int next = now + move[i]; // 다음 이동할 층 계산
                if(next<1 || next>F) continue; // 1층과 F층 사이의 층만 방문가능
                if(check[next]==false) { // 방문안한 층이면
                    dis[next]=dis[now]+1; // 한번의 이동 횟수 증가
                    check[next]= true; // 층 방문 체크
                    que.offer(next);
                }
            }
        }
        System.out.println("use the stairs");


    }
}

* 거리배열 사용

* BFS 이용

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다. 위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412 1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다. 가능한 명령어 나열이 여러가지면, 아무거나 출력한다.

*예제 입력 1 * 3 1234 3412 1000 1 1 16

*예제 출력 1 * LL L DDDD

풀이

1. 클래스 생성 : field - num, command / method - D,S,L,R
2. 10000개의 인덱스가 있는 방문배열 생성 => 방문한 각 숫자마다 체크
3. BFS로 각 숫자마다 D,S,L,R 확인하며 뻗어가기
4. 1. 방문배열이 방문됬다고 체크됬을 때 넘어간다
5. 2. 그 수가 방문을 안했을 때 방문배열 체크하고 큐에 넣기

public class Search_9019 {
    public static int N;
    //클레스 생성
    static class Register{
        public int num;
        public String command;
        public Register(int num, String command) {
            this.num = num;
            this.command = command;
        }

        public int D(int num){
            return (num*2)%10000;
        }

        public int S(int num){
            return (num==0) ? 9999 : num-1;
        }

        public int L(int num) {
            return (num%1000)*10 + num/1000;
        }

        public int R(int num) {
            return (num%10)*1000 + num/10;
        }



    }
    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());  

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int num1 = Integer.parseInt(st.nextToken()); // 출발숫자
            int num2 = Integer.parseInt(st.nextToken()); //도착숫자

            boolean[] isVisited = new boolean[10000]; // 각 시도 숫자마다 체크
            isVisited[num1] = true; //시작 숫자의 첫 방문

            Queue<Register> que = new LinkedList<Register>();
            que.offer(new Register(num1,"")); //처음 큐에 넣을 때는 명령은 빈칸

            while(!que.isEmpty()) {
                Register tmp = que.poll();
                if(tmp.num==num2) { // 도착숫자에 도달하면 출력 후 끝냄
                    System.out.println(tmp.command);
                    break;
                }
                // 숫자마다 각 명령어 모두 시도
                // 명령어 메소드에 리턴값을 숫자에 주입하고
                // 명령어는 기존 명령어 문자열 뒤에 추가한다.
                if(!isVisited[tmp.D(tmp.num)]) {
                    isVisited[tmp.D(tmp.num)]=true;
                    que.offer(new Register(tmp.D(tmp.num),tmp.command+"D"));
                }

                if(!isVisited[tmp.S(tmp.num)]) {
                    isVisited[tmp.S(tmp.num)]=true;
                    que.offer(new Register(tmp.S(tmp.num),tmp.command+"S"));
                }

                if(!isVisited[tmp.L(tmp.num)]) {
                    isVisited[tmp.L(tmp.num)]=true;
                    que.offer(new Register(tmp.L(tmp.num),tmp.command+"L"));
                }

                if(!isVisited[tmp.R(tmp.num)]) {
                    isVisited[tmp.R(tmp.num)]=true;
                    que.offer(new Register(tmp.R(tmp.num),tmp.command+"R"));
                }
            }
        }
    }


}

* 한 부분에서 결과가 유지되며 이어 나가진다 => BFS

* 객체마다 필요한 메소드는 클래스 내에 구현

* 왼쪽으로 밀기 (num%1000)*10 + num/1000;

* 오른쪽으로 밀기 (num%10)*1000 + num/10