섹션1. 시뮬레이션 & 구현 - (1) | 사다리타기, 로봇 문제 풀이

🎈섹션1. 시뮬레이션 & 구현

시뮬레이션 & 구현 알고리즘

• 어떤 개체가 이동하는 것을 코드 상으로 구현한 것
• (상/하/좌/우) 이동
• 문제를 해석하고 해석한 내용을 코드로 구현하는 게 중요하다.

🟦 1-1. 사다리 타기

문제

현수네 반에는 n명의 학생이 있습니다. 선생님은 n명의 학생이 모두 사다리타기를 한 다음 당첨
된 학생을 이 번주 학급회장으로 선출하려고 합니다.
각 학생은 알파벳 대문자로 표시됩니다.
만약 n=5 이고 아래와 같은 사다리라면 위에 사다리는 세로 라인이 1부터 5까지로 표현는 5개의 세로줄과 3개의 가로줄을 가지고 있습니다.

첫 번째 가로줄은 1번 세로줄과 2번 세로줄을 연결한 가로막대와 3번 세로줄과 4번 세로줄을 연결한 가로막대 2개가 있는데 이를 표현하는 방법은 [1, 3]으로 표현합니다.

즉 가로막대가 연결하고 있는 세로줄 중 왼쪽 세로줄 번호만 알려주는 형식입니다.

예를 들어 어떤 가로줄의 입력정보가 [1, 3, 5]로 표현된다면 이 가로줄에는 1번 세로줄과 2번 세로줄은 연결한 가로막대, 3번 세로줄과 4번 세로줄은 연결한 가로막대, 5번 세로줄과 6번 세로줄은 연결한 가로막대 이렇게 3개의 가로막대가 존재한다는 것입니다.
아래 그림처럼 가로줄의 정보는 [1, 2]와 같이 두 가로막대가 직접연결되는 경우는 입력되지 않
습니다. 위에 사다리의 정보는 [[1, 3], [2, 4], [1, 4]]와 같이 첫 번째 가로줄부터 순서대로 입력정보가
2차원 배열로 주어집니다. 사다리를 타는 학생은 알파벳순으로 1번 세로줄부터 순서대로 사다리를 탑니다.
매개변수 n에 학생수, ladder에 사다리의 정보가 주어지면, 모든 학생이 사다리를 탄 결과를 담
은 배열을 반환하는 프로그램을 작성하세요.

문제 풀이

• 가로줄을 만났을 때 위치 교환이 되는 매커니즘을 이해해야 한다.

코드

/* 1-1. 사다리 타기 | 자리교환 
 * */
import java.util.*;
class Solution1 {
    public char[] solution(int n, int[][] ladder){
        char[] answer = new char[n];

        //우선 기본 answer는 대문자 A ~ 차례로 세팅 초기화
        for(int i=0; i<n; i++) {
            answer[i] = (char)(i+65);
        }

        //실질적인 자리 교환 로직
            //1) 사다리 각 가로줄 뽑아옴 
        for(int[] line : ladder) {
                //2) 뽑아온 가로줄 차례로 탐색  
            for(int x: line) {
                char tmp = answer[x];
                answer[x] = answer[x-1];
                answer[x-1] = tmp;
            }
        }
        return answer;
    }

    //실행 메인 
    public static void main(String[] args){
        Solution1 T = new Solution1();
        System.out.println(Arrays.toString(T.solution(5, new int[][]{{1, 3}, {2, 4}, {1, 4}})));
        System.out.println(Arrays.toString(T.solution(7, new int[][]{{1, 3, 5}, {1, 3, 6}, {2, 4}})));
        System.out.println(Arrays.toString(T.solution(8, new int[][]{{1, 5}, {2, 4, 7}, {1, 5, 7}, {2, 5, 7}})));
        System.out.println(Arrays.toString(T.solution(12, new int[][]{{1, 5, 8, 10}, {2, 4, 7}, {1, 5, 7, 9, 11}, {2, 5, 7, 10}, {3, 6, 8, 11}})));
    }
}

---

🟦 1-2. 청소 | 상하좌우 이동

문제

청소 로봇이 방을 청소하려고 합니다. 방은 n*n 격자판 지도로 표현됩니다. 방에는 장애물(1로 표시)이 있고, 장애물이 있는 지점은 로봇이 지나갈 수 없습니다.
로봇은 지도의 왼쪽 가장 위 격자에서 3시 방향(오른쪽)을 보고 있습니다.
로봇이 한 격자를 이동하는데 걸리는 시간은 1초입니다.
로봇은 매초 한 칸씩 보고 있는 방향으로 이동합니다.

만약 지도 끝으로 이동해 더 이상 전진 할 수 없거나 또는 장애물을 만나면 제자리에서 시계방향으로 90도 회전합니다.

회전하는데도 1초의 시간이 필요합니다.
매개변수 board에 방의 지도정보가 주어지고, k에 초시간이 주어지면 로봇이 움직이기 시작해서 k초 후에 멈춥니다. k초 후 로봇의 위치를 반환하는 프로그램을 작성하세요.

문제풀이

• 상하좌우 이동을 위한 변수 선언이 중요하다.

코드

/* 1-2. 청소 | 로봇이 상하좌우 위치로 이동함
 * */
import java.util.*;
class Solution2 {
    //솔루션 함수 
    public int[] solution(int[][] board, int k){
        int[] answer = new int[2];  //반환용 답 
        int n = board.length; //격자판 크기
        //위치 이동 변수 : 12. 3. 6. 9 시계방향 순 
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        int d = 1, x= 0, y=0, count=0; 
        while(count < k) {
            count++;//반복 조건 
            int nx = x + dx[d];
            int ny = y + dy[d];
            // 격자밖 or 장애물 만날 경우 = 회전 해야 함 
            if(nx <0 || nx >= n || ny <0 || ny >=n || board[nx][ny] == 1) {
                d = (d+1) % 4;//계속 시계방향으로 회전 처리해야 하고
                //회전 시에도 시간 걸리므로 위치 동일해야 함 
                continue;
            }
            //좌표 찍어주고
            x = nx;
            y = ny; 
        }
        //반복문 탈출 후, 정답에 각각 x,y 최종 좌표 담기 
        answer[0] = x;
        answer[1] = y;

        return answer;
    }

    //실행 메인 
    public static void main(String[] args){
        Solution2 T = new Solution2();
        int[][] arr1 = {{0, 0, 0, 0, 0}, 
            {0, 1, 1, 0, 0}, 
            {0, 0, 0, 0, 0}, 
            {1, 0, 1, 0, 1}, 
            {0, 0, 0, 0, 0}};
        System.out.println(Arrays.toString(T.solution(arr1, 10)));
        int[][] arr2 = {{0, 0, 0, 1, 0, 1}, 
            {0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 1}, 
            {1, 1, 0, 0, 1, 0}, 
            {0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0}};
        System.out.println(Arrays.toString(T.solution(arr2, 20)));
        int[][] arr3 = {{0, 0, 1, 0, 0}, 
            {0, 1, 0, 0, 0}, 
            {0, 0, 0, 0, 0}, 
            {1, 0, 0, 0, 1}, 
            {0, 0, 0, 0, 0}};
        System.out.println(Arrays.toString(T.solution(arr3, 25)));

    }
}