developer-ellen
인간 디버거의 로그 찍기
developer-ellen
전체 방문자
오늘
어제
  • 분류 전체보기 (217)
    • 회고록 (0)
    • 취뽀 및 커리어 여정의 Stack (2)
      • SSAFY 7기 (2)
    • 프로그래밍공부 (24)
      • c++ (0)
      • JAVA (3)
      • Spring (5)
      • design pattern (3)
      • BackDB (1)
      • Servlet&JSP (3)
      • Vue (4)
      • JPA (4)
      • Infra (1)
      • Linux (0)
    • AI (3)
      • papers (3)
      • trend (0)
    • 프로젝트진행 (0)
      • 데이터베이스 (0)
      • 서버개발 (0)
      • 인공지능 (0)
      • 하루정리 (0)
    • 포트폴리오 (0)
    • 알고리즘 (158)
      • 알고리즘문풀 (155)
      • 알고리즘공부 (3)
    • 통계공부 (15)
      • 시계열분석 (15)
      • 회귀분석 (0)
    • CS (14)
      • 컴퓨터네트워크 (4)
      • 운영체제 (8)
      • 데이터베이스 (2)
    • 주저리주저리 (0)
      • 필사 (0)
    • 취업관련정보 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • ARIMA모형
  • 운영체제인터럽트
  • SW역량테스트파이썬풀이
  • 삼성코테파이썬
  • 통계학
  • 삼성코테구현풀이
  • 카카오코테
  • c++ 빌더 패턴
  • 시계열분석
  • 삼성코테자바준비
  • 시계열
  • 데이터분석
  • 코테파이썬
  • MA모형
  • 삼성코테자바꿀팁
  • 삼성코테기출
  • c++디자인패턴
  • 백준파이썬풀이
  • BOJ파이썬풀이
  • AR모형
  • SW역량테스트파이썬
  • 삼성코테파이썬풀이
  • 카카오코테java풀이
  • 삼성코테기출자바풀이
  • 통계분석
  • Arima
  • 삼성코테구현문제추천
  • 삼성코테파이썬준비
  • 삼성코테자바풀이
  • 삼성코테준비

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
developer-ellen
알고리즘/알고리즘문풀

BOJ - 주사위 굴리기2 23288번 (JAVA)

알고리즘/알고리즘문풀

BOJ - 주사위 굴리기2 23288번 (JAVA)

2022. 3. 4. 00:56

❓ 문제 - 백준 주사위 굴리기2 23288번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/23288)

 

23288번: 주사위 굴리기 2

크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼

www.acmicpc.net

 

 

📝 문제해결법

1. 이 문제는 시뮬레이션 + BFS 으로 문제를 풀었다.

  • K번의 주사위를 굴릴 때 현재 방향으로 이동한 뒤 점수 계산을 위해 그 이동한 곳에 위치에 있는 점수와 같은 점수가 몇 개 인접했는지 카운트 하는 것을 BFS로 구현하였다. 
  • 전체 구현 흐름은 다음과 같다. 주사위의 방향으로 이동해보고 만약 범위를 벗어나는 곳으로 이동하지 못한다면 이동방향을 바꿔서 그곳으로 이동하게 구현한다.
  • 또한 dice라는 배열을 만들어서 주사위의 윗면-뒷면-오옆-왼옆-앞면-바닥면을 각 인덱스에 맞춰서 주사위 숫자를 넣어준다.
  • 그리고 change_dice()라는 함수를 통해 주사위를 굴려진 방향에 맞춰서 각 면에 바껴진 주사위 숫자를 갱신한다.
  • BFS로 해당 위치에 적힌 점수와 같은 점수가 몇 개 인접했는지 카운트 해줘서 카운트 갯수 * 적힌 점수 해서 점수를 증가시켜준다.
  • 그리고 주사위의 바닥면과 map에 적힌 숫자와 비교해서 문제에 주어진 조건대로 주사위의 이동방향을 바꾼다.
  • 만약 주사위 바닥면의 숫자가 map에 적힌 숫자보다 크다면 시계방향으로 변경 처리, 그리고 주사위 바닥면의 숫자가 map에 적힌 숫자보다 작다면 반시계방향 변경 처리, 그리고 두 숫자가 같다면 방향 처리를 하지 않는다.

2. 주사위 굴러가는 방향에 맞춰 주사위 면의 값 변경 => change_dice()

  • dice 인덱스에 맞는 각 주사위 면은 윗면(0)-뒷면(1)-오옆(2)-왼옆(3)-앞면(4)-바닥면(5)
  • 만약 동쪽으로 주사위가 굴러가면 윗면->오옆->아랫면->왼옆->윗면 으로 주사위의 값이 변경된다.
  • 만약 남쪽으로 주사위가 굴러가면 윗면->앞면->바닥면->뒷면->앞면 으로 주사위의 값이 변경된다.
  • 만약 서쪽으로 주사위가 굴러가면 윗면->왼옆->바닥면->오옆->윗면 으로 주사위의 값이 변경된다.
  • 만약 북쪽으로 주사위가 굴러가면 윗면->뒷면->바닥면->앞면->윗면 으로 주사위의 값이 변경된다.
  public static void change_dice(){
  		// 동쪽
        if(dir == 0){
            int temp = dice[0];
            dice[0] = dice[3];
            dice[3] = dice[5];
            dice[5] = dice[2];
            dice[2] = temp;

        } else if(dir == 1){  // 남쪽
            int temp = dice[0];
            dice[0] = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[4];
            dice[4] = temp;
        } else if(dir == 2){ // 서쪽
            int temp = dice[0];
            dice[0] = dice[2];
            dice[2] = dice[5];
            dice[5] = dice[3];
            dice[3] = temp;
        } else if(dir == 3){ // 북쪽
            int temp = dice[0];
            dice[0] = dice[4];
            dice[4] = dice[5];
            dice[5] = dice[1];
            dice[1] = temp;
        }
    }

 

3. 느낀점

  • 기존 삼성기출의 주사위굴리기1을 풀어보면 거기에 bfs만 추가하여 구현하면 될 것이라고 느꼈다...
  • 시뮬레이션의 핵심은 주어진 조건에 맞춰 잘 구현하면 되는 것이다...
  • 주사위가 굴러갔을 때 굴러간 방향에 맞춰 주사위 면들의 값들이 변경되는 부분을 신경 잘 써서 구현해야 한다!!

 

💻 소스코드

// BOJ - 주사위굴리기2(23288번)
// 구현 + BFS

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

public class Main_23288 {
    // 윗면 - 뒷면 - 오옆 - 왼옆 - 앞면 - 바닥면
    public static int[] dice = {1, 2, 3, 4, 5, 6};

    // 동 - 남 - 서 - 북
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {1, 0, -1, 0};
    public static int[][] map;
    public static int N, M, K, dir;
    public static int d_x, d_y;
    public static class Node {
        int x;
        int y;
        public Node(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));
        StringBuilder sb = new StringBuilder();
        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+1][M+1];

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

        dir = 0;
        int score = 0;
        int rotate_cnt = 1;
        d_x = 1;
        d_y = 1;
        while (rotate_cnt++ <= K){
            // 해당 방향으로 이동
            d_x += dx[dir];
            d_y += dy[dir];
            // 이동할 수 없는 곳 ?
            if(d_x < 1 || d_x > N || d_y < 1 || d_y > M){
                d_x -= dx[dir];
                d_y -= dy[dir];
                // 이동방향 반대로 전환
                dir = (dir+2) % 4;
                d_x += dx[dir];
                d_y += dy[dir];
            }

            // 주사위 면 변화
            change_dice();
            int cnt = bfs();
            // 점수 획득
            score += (cnt*map[d_x][d_y]);

            // 이동방향 변경
            if(dice[5] > map[d_x][d_y]){
                dir = (dir + 1) % 4;
            } else if(dice[5] < map[d_x][d_y]){
                dir = (dir==0?3:dir-1);
            }
        }

        sb.append(score);
        System.out.println(sb.toString());
    }

    public static void change_dice(){
        if(dir == 0){
            int temp = dice[0];
            dice[0] = dice[3];
            dice[3] = dice[5];
            dice[5] = dice[2];
            dice[2] = temp;

        } else if(dir == 1){
            int temp = dice[0];
            dice[0] = dice[1];
            dice[1] = dice[5];
            dice[5] = dice[4];
            dice[4] = temp;
        } else if(dir == 2){
            int temp = dice[0];
            dice[0] = dice[2];
            dice[2] = dice[5];
            dice[5] = dice[3];
            dice[3] = temp;
        } else if(dir == 3){
            int temp = dice[0];
            dice[0] = dice[4];
            dice[4] = dice[5];
            dice[5] = dice[1];
            dice[1] = temp;
        }
    }

    public static int bfs(){
        boolean[][] visited = new boolean[N+1][M+1];
        int cnt = 1;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(d_x, d_y));
        visited[d_x][d_y] = true;
        while (!q.isEmpty()){
            Node node = q.poll();
            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];

                if(1 <= nx && nx <= N && 1 <= ny && ny <= M){
                    if(!visited[nx][ny] && map[nx][ny] == map[d_x][d_y]){
                        visited[nx][ny] = true;
                        cnt++;
                        q.offer(new Node(nx, ny));
                    }
                }
            }
        }
        return cnt;
    }


}

 

 

 

'알고리즘 > 알고리즘문풀' 카테고리의 다른 글

BOJ - 녹색 옷 입은 애가 젤다지? 4485번 (JAVA)  (0) 2022.03.08
BOJ - 서강그라운드 14938번 (JAVA)  (0) 2022.03.07
BOJ - 마법사 상어와 복제 23290번 (JAVA)  (0) 2022.03.01
BOJ - 입국심사 3079번 (JAVA)  (0) 2022.02.21
BOJ - 빙산 2573번 (JAVA)  (0) 2022.02.19
  • ❓ 문제 - 백준 주사위 굴리기2 23288번 - JAVA 풀이법
  • 📝 문제해결법
  • 💻 소스코드
'알고리즘/알고리즘문풀' 카테고리의 다른 글
  • BOJ - 녹색 옷 입은 애가 젤다지? 4485번 (JAVA)
  • BOJ - 서강그라운드 14938번 (JAVA)
  • BOJ - 마법사 상어와 복제 23290번 (JAVA)
  • BOJ - 입국심사 3079번 (JAVA)
developer-ellen
developer-ellen

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.