[ 코드트리 조별과제 ] 프로그래밍 연습 - Chapter5. 시뮬레이션(2)

 1. 최장연속 부분수열 

 

수열 (2, 2, 7, 7, 7, 7, 5, 7, 7)이 주어졌을 때, 연속해서 나오는 같은 숫자를 한 묶음이라 봤을 때, 총 몇 개의 묶음이 있을까요?

 

i번째 index에 해당하는 원소를 a[i]라 했을 때 a[i] ≠ a[i - 1] 인 경우를 찾으면 된다.

그러나 i가 0인 경우에는 직전 원소를 정의할 수 없으므로, 따로 예외적으로 처리를 해줘야 함에 유의해야한다.

즉, 연속수열의 수를 세는 조건은 i가 0이거나 a[i] ≠ a[i - 1]인 경우가 된다.

int cnt = 0;
for(int i = 0; i < n; i++)
    if(i == 0 || a[i] != a[i - 1])
        cnt++;

System.out.print(cnt);

 

이때 인덱스 비교조건( a[i] ≠ a[i - 1] )을 먼저 수행하면 i가 0인 경우에 a[i] ≠ a[i - 1] 에 대한 비교를 진행하게 되기 때문에 Runtime error가 발생하게 된다.

if(i == 0 || a[i] != a[i - 1])

 

 

[ 개념문제 ]

N개의 숫자들이 주어졌을 때, 연속하여 동일한 숫자가 나오는 횟수 중 최대를 구하는 프로그램을 작성해보세요.
첫 번째 줄에 N이 주어집니다.
두 번째 줄부터 N개의 줄에 걸쳐 각 숫자들이 한 줄에 하나씩 주어집니다.
1 ≤ N ≤ 1,000 
0 ≤ 입력으로 주어지는 숫자 ≤ 1,000

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] num = new int[n];
        for(int i=0; i<n; i++) num[i] = sc.nextInt();

        int cnt = 0;
        int max = 0;
        for(int i=0; i<n; i++){
            if(i==0 || num[i]==num[i-1]){
                cnt++;
            } else {
                cnt = 1;
            }
            if(cnt>=max) max = cnt;
        }

        System.out.println(max);
    }
}

 

 

---

 

 

 2. 배열기록 

 

계속 유지해야 하는 정보가 있는 경우에는 배열을 활용해 그 값을 기록해놓는 방식으로 진행하는 것이 좋다.

 

[ 응용문제 ] 좌우로 움직이는 로봇

1차원 직선 위에서 1초에 한 칸씩 좌우로만 왔다 갔다 하는 로봇 A와 B가 있습니다. A가 움직이는 횟수 n와 B가 움직이는 횟수 m이 주어지고 각각 로봇들이 어느 방향으로 얼만큼 움직였는지가 주어졌을 때, 로봇 A와 B가 
바로 직전에는 다른 위치에 있다가 그 다음 번에
 같은 위치에 오게 되는 경우가 총 몇 번인지를 구하는 프로그램을 작성해봅니다. 단, 로봇 A, B는 처음에 같은 지점에서 움직이며 이는 횟수에 포함시키지 않습니다. 또한, 각 로봇이 움직임을 종료한 이후에는 같은 위치에 계속 머물러 있으며 이때 역시 다른 로봇이 움직임에 따라 두 로봇이 같은 위치에 오게될 수 있습니다. 다만, 모든 로봇이 움직인 이후의 상황은 생각하지 않습니다.

첫 번째 줄에 각 로봇이 움직인 횟수 n과 m이 각각 공백을 사이에 두고 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 로봇 A가 움직인 정보가 (t, d) 형태로 공백을 사이에 두고 주어집니다. t초 만큼 방향 d로 이동함을 의미하며, d는 ‘L', 또는 'R’로만 주어집니다.
그 다음 줄 부터는 m개의 줄에 걸쳐 로봇 B가 움직인 정보가 (t, d) 형태로 공백을 사이에 두고 주어집니다. 로봇 A와 B 모두 움직인 거리의 총 합은 1,000,000을 넘지 않음을 가정해도 좋습니다.
1 ≤ n, m ≤ 50,000

 

 

테스트 케이스

4 5
3 L
5 R
1 L
2 R
4 R
1 L
3 L
4 R
2 L

시간 7, 9, 13일때 두 로봇은 서로 마주친다. 10, 11초에도 같은 위치에 있기는 하지만, 바로 직전에도 같은 위치에 있었으므로 횟수로 세지 않는다.

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //a의 움직임
        int m = sc.nextInt(); //b의 움직임

        int[] timeA = new int[n];
        char[] distA = new char[n];
        int[] timeB = new int[m];
        char[] distB = new char[m];

        int timesizeA = 0; //a의 총이동시간
        for(int i=0; i<n; i++) {
            int time = sc.nextInt();
            timesizeA += time;
            timeA[i] = time;
            distA[i] = sc.next().charAt(0);
        }

        int timesizeB = 0; //b의 총이동시간
        for(int i=0; i<m; i++) {
            int time = sc.nextInt();
            timesizeB += time;
            timeB[i] = time;
            distB[i] = sc.next().charAt(0);
        }

        int size = Math.max(timesizeA, timesizeB); //더 큰 사이즈
        int[] locationA = new int[size+1];
        int[] locationB = new int[size+1];

        int location = 0;
        int idx = 0; //다음 시간의 인덱스
        for(int i=0; i<n; i++){
            if(distA[i]=='R'){
                for(int j=1; j<=timeA[i]; j++){
                    location++;
                    locationA[idx+j] = location;
                }
            } else {
                for(int j=1; j<=timeA[i]; j++){
                    location--;
                    locationA[idx+j] = location;
                }
            }
            idx += timeA[i]; //진행하는 시간만큼 인덱스 증가
        }

        location = 0;
        idx = 0;
        for(int i=0; i<m; i++){
            if(distB[i]=='R'){
                for(int j=1; j<=timeB[i]; j++){
                    location++;
                    locationB[idx+j] = location;
                }
            } else {
                for(int j=1; j<=timeB[i]; j++){
                    location--;
                    locationB[idx+j] = location;
                }
            }
            idx += timeB[i];
        }

        //먼저 종료된 경우 마지막 숫자로 채우기
        int min = Math.min(timesizeA, timesizeB);
        if(timesizeA < timesizeB){
            for(int i=min+1; i<=size; i++){
                int last = locationA[min];
                locationA[i] = last;
            }
        } 
        if(timesizeA > timesizeB){
            for(int i=min+1; i<=size; i++){
                int last = locationB[min];
                locationB[i] = last;
            }
        }
        // for(int i=0; i<=size; i++) System.out.print(locationA[i]+" ");
        // System.out.println();
        // for(int i=0; i<=size; i++) System.out.print(locationB[i]+" ");
        // System.out.println();
        
        int cnt = 0;
        int index = 1;
        while(index <= size){
            if( locationA[index]==locationB[index] && locationA[index-1]!=locationB[index-1] ) {
                cnt++;
            }
            index++;
        }

        System.out.println(cnt);

    }
}

 

A와 B의 총 이동시간이 다를 수 있다. 움직임을 종료한 이후에는 같은 위치에 계속 머물러 있기에 더 큰 만큼 공간을 만들어주고 마지막 위치로 채워주어야 마지막 일치점까지 비교할 수 있었다. idx변수를 만들어 시간 흐름 반영을 기록해야한다.

 

---

 

 

[ 응용문제 ] 선두를 지켜라3

A와 B가 동일한 시작점에서 같은 방향으로 출발합니다. 도중에 방향을 바꾸는 경우는 없고, A, B는 각각 N번, M번에 걸쳐 주어지는 특정 속도로 특정 시간만큼 이동한다고 합니다. 이 경기는 특이하게 매 시간마다 현재 선두인 사람들을 모아 명예의 전당에 그 이름을 올려줍니다. A, B의 움직임에 대한 정보가 주어졌을 때 명예의 전당에 올라간 사람의 조합이 총 몇 번 바뀌었는지를 출력하는 프로그램을 작성해보세요.

첫 번째 줄에 N과 M이 주어집니다.
두 번째 줄부터는 N개의 줄에 걸쳐 각 줄마다 A가 어떤 속도로 몇 시간 동안 이동했는지를 나타내는 (v, t) 값이 공백을 사이에 두고 주어집니다.
그 다음 줄부터는 M개의 줄에 걸쳐 각 줄마다 B가 어떤 속도로 몇 시간 동안 이동했는지를 나타내는 (v, t) 값이 공백을 사이에 두고 주어집니다.
A가 총 이동한 시간과 B가 총 이동한 시간은 항상 동일하게 주어짐을 가정해도 좋습니다.
1 ≤ N, M ≤ 1,000
1 ≤ v, t ≤ 1,000

첫 번째 줄에 명예의 전당에 올라간 사람의 조합이 총 몇 번 변경 되었는지를 출력해주세요.

 

테스트 케이스

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

 

 

처음 3시간 동안은 B가 명예의 전당에 올라가 있고 이후에는 A, B가 동시에 명예의 전당에 올라가게 된다. 이후 A 혼자 명예의 전당에 올라가게 되었다가 시작으로부터 6시간이 흐른 뒤에는 A, B가 동시에 명예의 전당에 올라가게 된다. 이후에는 다시 B 혼자 명예의 전당에 올라가게 되므로 총 5번 조합이 바뀌게 된다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        //a의 움직입
        int[] locationA = new int[1000*n];
        int index = 1;
        int start = locationA[0];
        for(int i=0; i<n; i++){
            int velocity = sc.nextInt();
            int time = sc.nextInt();
            for(int j=1; j<=time; j++){
                start += velocity;
                locationA[index++] = start;
            }
        }
        //for(int i=0; i<locationA.length; i++) System.out.print(locationA[i]+" ");

        //b의 움직입
        int[] locationB = new int[1000*m];
        index = 1;
        start = locationB[0];
        for(int i=0; i<m; i++){
            int velocity = sc.nextInt();
            int time = sc.nextInt();
            for(int j=1; j<=time; j++){
                start += velocity;
                locationB[index++] = start;
            }
        }

        int cnt = 0;
        int idx = 1;
        int size = Math.min(locationA.length, locationB.length);
        while( idx<size ){
            if( locationA[idx] > locationB[idx] && locationA[idx-1] <= locationB[idx-1] ) cnt++;
            if( locationA[idx] < locationB[idx] && locationA[idx-1] >= locationB[idx-1] ) cnt++;
            if( locationA[idx] == locationB[idx] && locationA[idx-1] != locationB[idx-1] ) cnt++;
            idx++;
        }
        System.out.println(cnt-1);
    }
}

 

처음에 같은 경우는 배제하기 위해 마지막 cnt에서 1을 뺀 값으로 출력한다.

 

---

 

[ 어려웠던 문제 ] 악수와 전염병의 상관관계2

N명의 개발자들이 있으며, T번에 걸쳐 t초에 x개발자가 y개발자와 악수를 나눈 정황이 주어집니다. 1명의 개발자가 처음에 이 전염병을 옮기기 시작한 것이 확실해 졌고, 개발자가 이 병에 감염된 후에는 정확히 K번의 악수 동안만 전염병을 옮기게 되고, 그 이후부터는 전염병에 걸려있지만 새로 옮기지는 않게 됩니다. 개발자들의 악수에 대한 정보와 처음 전염병에 걸려 있는 개발자의 번호 P가 주어졌을 때, 모든 악수를 진행한 이후에 최종적으로 누가 전염병에 걸리게 되었는지를 알아내는 프로그램을 작성해보세요.
단, 전염된 사람끼리 만나도 전염시킨 것으로 간주해야 합니다. 예를 들어 전염된 x 개발자와 전염된 y 개발자끼리 악수를 해도 전염병을 옮기게 되는 횟수에 포함시켜야 합니다. 이때, 감염 횟수에 포함될 뿐, 이미 전염되었던 사람이 재감염이 되는 것은 아님에 유의합니다.

첫 번째 줄에 정수 N, K, P, T가 각각 공백을 사이에 두고 주어집니다.
두 번째 줄부터는 T개의 줄에 걸쳐 각 줄마다 t, x, y에 대한 정보가 공백을 사이에 두고 주어집니다. 이는 t초에 x 개발자와 y 개발자가 악수를 나눴음을 의미하고, x, y 값은 항상 다르게 주어짐을 가정해도 좋습니다. 또한, 입력으로 주어지는 t값은 모두 다름을 가정해도 좋습니다.

첫 번째 줄에 N명의 개발자에 대한 최종 감염 여부를 첫 번째 개발자부터 순서대로 N 번째 개발자까지 공백없이 출력합니다. 각 개발자 마다 출력해야 할 값은 0 또는 1이며, 0은 음성을 1은 양성을 뜻합니다.

2 ≤ N ≤ 100, 1 ≤ K ≤ 250, 1 ≤ P ≤ N, 1 ≤ T ≤ 250, 1 ≤ t ≤ 250

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); //개발자 수
        int K = sc.nextInt(); //최대 전염횟수
        int P = sc.nextInt(); //첫 감염자
        int T = sc.nextInt(); //진행 횟수

        int[] infected = new int[N]; //감염여부
        infected[P-1] = 1;
        int[] con = new int[N];      //전염횟수

        //입력값 받기
        int[][] inputs = new int[T][3];
        for(int i=0; i<T; i++){
            for(int j=0; j<3; j++){
                inputs[i][j] = sc.nextInt();
            }
        }
        //입력값 정렬
        Arrays.sort( inputs, (a, b) -> Integer.compare(a[0], b[0]) ); //첫번째 열 기준

        
        for(int i=0; i<T; i++){
            int x = inputs[i][1]-1;
            int y = inputs[i][2]-1;
            //둘다 감염자일때 -> x의 전염횟수 증가, y의 전염횟수 증가
            //x만 감염자일때 -> x의 전염횟수 증가, y가 전염자됨
            //y만 감염자일때 -> y의 전염횟수 증가, x가 전염자됨
            if(infected[x]==1 && con[x] < K && infected[y]==1 && con[y] < K){
                con[x]++;
                con[y]++;
            } else if(infected[x]==1 && con[x] < K){
                con[x]++;
                infected[y]=1;
            } else if(infected[y]==1 && con[y] < K){
                con[y]++;
                infected[x]=1;
            }

            //if문을 따로 돌릴경우 감염과 동시에 횟수가 증가 -> 3가지 경우
        }

        for(int i=0; i<N; i++) System.out.print(infected[i]);

    }
}

 

 

어려웠던 점

마지막 for문 처리에서 x가 감염자인경우, y가 감염자인 경우를 각각 다른 if문으로 2개 구비해놓았다.

이러한 경우 발생하는 문제는 감염자 x가 비감염자인 y를 감염시키고 난뒤 한번더 if문이 돌아가서 y가 x를 다시 감염시킨 처리가 되었다. else if문을 통해 감염처리가 한번만 이루어지도록 하였고 둘다 감염자인 경우도 처음에 검사하도록 따로 빼 두어야했다.

 

 

---

 

 

 

 3. dx dy technique 

특정방향에 대한 이동이 반복되는 코드에는  dx, dy 테크닉을 사용할 수 있다.

 

[ 개념문제 ]

(x, y) 위치에서 시작하여 한 칸 이동하려 합니다.
숫자 0이 주어지면 동쪽으로, 숫자 1이 주어지면 남쪽으로, 숫자 2가 주어지면 서쪽으로, 숫자 3이 주어지면 북쪽으로 이동하려 합니다.

 

기본적인(수학적) 방법

int dirNum = ??;   	// 주어진 방향( 0~3 )
int x = 0, y = 0; 	// 현재 위치
int nx, ny;		// 이동후 위치

if(dirNum == 0) {
    nx = x + 1; ny = y;
}
else if(dirNum == 1) {
    nx = x; ny = y - 1;
}
else if(dirNum == 2) {
    nx = x - 1; ny = y;
}
else {
    nx = x; ny = y + 1;
}

 

 

dx, dy 테크닉 : 각 방향에 맞는 x좌표, y좌표의 차이를 배열 dx, dy로 선언하여 간단하게 해결한다.

int dirNum = ??;   	// 주어진 방향
int x = 0, y = 0; 	// 현재 위치
int[] dx = new int[]{1,  0, -1, 0}; 	//동, 남, 서, 북 순서
int[] dy = new int[]{0, -1,  0, 1};	//동, 남, 서, 북 순서
int nx, ny;

nx = x + dx[dirNum];
ny = y + dy[dirNum];

 

 

---

 

회전하여 이동하기

시계방향 순서대로 dx, dy를 정의하고 회전시에 적절하게 값을 변경시킨다. ( 위치체계를 변경시킨다. )

 

시계방향으로 90도 회전하는 경우 순서대로 정의된 dx, dy에 1을 더하고 4로 나눈 나머지를 구한다.

반시계방향으로 90도 회전하는 경우 순서대로 정의된 dx, dy에 3을 더하고 4로 나눈 나머지를 구한다.

 

회전방향에 따 적절한 양수 값을 갖도록 만들어 주는 것이 중요하다. ( 단순히 1을 더하면 값이 최고값이 초과되고 -1을 하면 값이 최소값이 모자라진다. )

 

 

 

[ 개념문제 ]

좌표평면 위 (0, 0)에서 북쪽을 향한 상태에서 움직이는 것을 시작하려 합니다. N개의 명령에 따라 총 N번 움직이며, 명령 L이 주어지면 왼쪽으로 90도 방향 전환을, 명령 R이 주어지면 오른쪽으로 90도 방향전환을 하고, 명령 F가 주어지면 바라보고 있는 방향으로 한칸 이동하려고 합니다. 이동 이후 최종 위치를 출력하는 프로그램을 작성해보세요.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int x=0, y=0; //현위치
        int[] dx = new int[]{ 0, 1, 0, -1 }; //북, 동, 서, 남 방향
        int[] dy = new int[]{ 1, 0, -1, 0 };
        int dir = 0; //위치 인덱스

        String input = sc.next();
        for(int i=0; i<input.length(); i++){
            char order = input.charAt(i);
            if(order=='R') dir = (dir+1) % 4; //시계방향 90도 회전
            if(order=='L') dir = (dir+3) % 4; //반시계방향 90도 회전
            if(order=='F'){
                x += dx[dir];
                y += dy[dir];
            }
        }

        System.out.println(x+" "+y);

    }
}

 

 

---

 

행렬에서 이동하기

2차원 배열로 표현된 행렬에서 상하좌우 움직임을 dx,dy 테크닉을 이용하여 해결할 수 있다.

좌표상의 x,y가 아닌 행과 열로 생각하여 dx, dy 배열의 정의한다. ( 열과 행 번호의 증가, 감소로 생각한다. )

 

 

 

상하좌우의 움직임이 정의된 행렬(2차원배열)의 범위 내에서 유효한지 확인하는 작업이 필요하다.

inRange 함수를 별도로 정의하여 활용한다.

public static boolean inRange(int x, int y) {
    return (0 <= x && x < 열크기 && 0 <= y && y < 행크기 );
}

...

//유효한 범위내에서 조건을 만족하는 값 찾기
if(inRange(nx, ny) && a[nx][ny] == 1) ...

 

 

---

 

적절한 방향변환

특정 상황에서(조건을 만족) 방향을 뒤집는 작업은 방향에 따른 dx, dy 변환방식에 따라 적절하게 정의하여 해결할 수 있다.

 

0번 <-> 3번 / 1번 <-> 2번 : 반대방향의 인덱스의 합이 3으로 동일하도록 설정한다.

이처럼 방향 전환을 원활하게 할 수 있도록 dx, dy 순서를 센스있게 정의하는 것 역시 중요하다.

 

숫자 0과 1로만 이루어진 n * n 크기의 격자 상태가 주어집니다. 각 칸 중 상하좌우로 인접한 칸 중 숫자 1이 적혀 있는 칸의 수가 3개 이상인 곳의 개수를 세는 프로그램을 작성해보세요. 단, 인접한 곳이 격자를 벗어나는 경우에는 숫자 1이 적혀있지 않은 것으로 생각합니다.

첫 번째 줄에 n이 주어집니다.
두 번째 줄부터는 n개의 줄에 걸쳐 각 줄마다 각각의 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다. 전부 0과 1로 이루어져 있다고 가정해도 좋습니다.

import java.util.Scanner;

public class Main {
    public static boolean inRange(int x, int y, int n){ //행렬범위내 유효성 확인
        return ( x>=0 && x<n && y>=0 && y<n );
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[][] space = new int[n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                space[i][j] = sc.nextInt();
            }
        }

        int[] dx = new int[]{0, 1, 0, -1}; // 상, 우, 하, 좌 움직임
        int[] dy = new int[]{1, 0, -1, 0}; // 상, 우, 하, 좌 움직임

        int cntNum = 0;
        for(int x=0; x<n; x++){
            for(int y=0; y<n; y++){
                int cnt = 0; //근접한 1의 갯수
                for(int i=0; i<4; i++){ // 상하좌우 4회 test
                    int nx = x + dx[i]; // 새로운 x 위치 = 기존위치 + 상, 우, 하, 좌 움직임
                    int ny = y + dy[i]; // 새로운 y 위치 = 기존위치 + 상, 우, 하, 좌 움직임
                    if( inRange(nx,ny,n) && space[nx][ny]==1 ) cnt++; // 범위확인 -> 조건확인
                }
                if(cnt>=3) cntNum++;
            }
        }
        System.out.println(cntNum);
    }
}

 

 

[ 응용문제 ] 빙빙돌며 숫자 사각형 채우기

n * m크기의 직사각형에 숫자 1부터 순서대로 증가시키며 달팽이 모양으로 채우는 코드를 작성해보세요.
달팽이 모양이란 왼쪽 위 모서리에서 시작해서, 오른쪽, 아래쪽, 왼쪽, 위쪽 순서로 더 이상 채울 곳이 없을 때까지 회전하는 모양을 의미합니다.
n : 행(row), m : 열(column)을 의미합니다.

 

 

 

이차원 배열에서 dx dy 테크닉을 활용하여 해결할 수 있다.

순서대로 방향체계를 0~3으로  90' 틀어주는 방식으로 해결할 수 있다.

• 오른쪽 (direction = 0) : x(행)는 그대로, y(열)는 1 증가
• 아래쪽 (direction = 1) : x(행)는 1 증가, y(열)는 그대로
• 왼쪽 (direction = 2) : x(행)는 그대로, y(열)는 1 감소
• 위쪽(direction = 3) : x(행)는 1 감소, y(열)는 그대로

방향인덱스(direction)이 1씩 증가하게 되므로 그 다음 방향은 (dir + 1) % 4로 계산할 수 있다.

 

 

방향인덱스(direction)가 변경되는 2가지 경우의 수(case)

1) 그 다음 위치가 격자를 벗어난다면 다음 방향으로 바꾸어 진행한다.

2) 그 다음 위치가 이미 방문했던 곳(배열숫자가 0이 아닌 수로 채워져있음)이라면 다음방향으로 바꾸어 진행한다.

 

import java.util.Scanner;

public class Main {
    public static boolean inRange(int x, int y, int n, int m){
        return (x>=0 && x<n && y>=0 && y<m);
    }
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(); //행
        int m = sc.nextInt(); //열

        int[][] arr = new int[n][m];
        int[] dr = new int[]{ 0, 1, 0, -1 }; //우하좌상 순서(달팽이 모양)
        int[] dc = new int[]{ 1, 0, -1, 0 }; //우하좌상
        int dir = 0; 
        int r=0, c=0; //행렬인덱스
        arr[r][c] = 1;
        for(int i=2; i<=n*m; i++){
            //다음위치
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            // 행렬범위를 벗어나거나 이미 숫자가 존재한다면 방향변환(=90도 회전)
            if( !inRange(nr, nc, n, m) || arr[nr][nc] !=0 ) {
                dir = (dir+1)% 4;
                nr = r + dr[dir];
                nc = c + dc[dir];
            }

            //적절한 값으로 이동
            r = nr;
            c = nc;
            arr[r][c] = i;
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }

    }
}

 

어려웠던 점

dr, dc 정의시에 좌표와 헷갈려서 실수가 발생하였다. 

위쪽 방향으로 향하는 것이 행(r)에서는 감소가 되고 y축에서는 증가가된다. 

아래방향으로 향하는 것이 행(r)에서는 증가가 되고 y축에서는 감소가 된다.

이와달리 열(c)과 x축은 증가와 감소방향이 동일해서 헷갈리지 않았다.

 

 

[ 어려웠던 문제 ] 거울에 레이저 쏘기2

N * N 크기의 격자 안에 각 칸마다 거울이 하나씩 들어 있습니다. 각 거울은 \ 나 / 의 형태를 띄고있고, 격자 밖 4N개의 위치 중 특정 위치에서 레이저를 쏘았을 때, 거울에 튕기는 횟수를 구하는 프로그램을 작성해보세요.

첫 번째 줄에 N이 주어집니다.
두 번째 줄부터 N개의 줄에 걸쳐 맵의 정보가 주어집니다. 각 줄에는 각 행에 해당하는 정보가 공백없이 주어집니다. 이는 / 나 \ 문자로만 이루어져 있습니다.
그 다음 줄에는 레이저를 쏘는 위치 K가 주어집니다. K는 다음과 같이 위에서 아래 방향으로 1행 1열 칸으로 들어오는 곳을 1번으로 하여 시계 방향으로 돌며 가능한 시작 위치에 순서대로 번호를 붙여 4N 번을 마지막으로 했을 때의 번호들 중 하나의 값으로 주어집니다.
( 1 ≤ N ≤ 1000 , 1 ≤ K ≤ 4N )

 

 

 

거울의 모양과 만나는 방향에 따라 진행되는 반사방향이 달라진다.

/ : 상, 하 진입시 시계방향으로 진행
/ : 좌, 우 진입시 반시계 방향으로 진행
\ : 좌, 우 진입시 시계 방향으로 진행
\ : 상, 하 진입시 반시계방향으로 진행

 

시작방향을 고려하기 위해 한칸 더 큰 이차원배열을 만들어서 진행한다. 인덱스 설정을 제대로 못해서 힘들었다.

\의 경우 escape문자인 \를 한번더 포함해야 검색된다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] dr = new int[]{1, 0, -1, 0}; // 하, 좌, 상, 우
        int[] dc = new int[]{0, -1, 0, 1}; 

	//명령받기
        String[] input = new String[n];
        for(int i=0; i<n; i++) input[i] = sc.next();
        //이차원 배열 채우기
        char[][] space = new char[n+2][n+2];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                space[i][j] = input[i-1].charAt(j-1);
            }
        }
        // for(int i=0; i<n+1; i++){
        //     for(int j=0; j<n+1; j++){
        //         System.out.print(space[i][j]+" ");
        //     }
        //     System.out.println();
        // }
        
        int r = 0;
        int c = 0;
        int dir = 0;
        int k = sc.nextInt(); //처음 레이저 쏘는 위치
        //위치에 따른 방향 & 시작인덱스 설정
        if(k>=1 && k<=n) {
            dir = 0; //하
            r = 0;
            c = k;
        } else if(k>=n+1 && k<=2*n) {
            dir = 1; //좌
            r = k-n;
            c = n+1;
        } else if(k>=2*n+1 && k<=3*n) {
            dir = 2; //상
            r = n+1;
            c = -1*(k-3*n) + 1;
        } else if(k>=3*n+1 && k<=4*n) {
            dir = 3;
            r = -1*(k-4*n) + 1;
            c = 0;
        }

        /*
            /는 상<->우, 하<->좌
            \는 상<->좌, 하<->우
        */
        int cnt = 0;
        do {
            r = r + dr[dir];
            c = c + dc[dir];

            if(space[r][c]=='/' && (dir==0||dir==2)) dir = (dir+1)%4;
            else if(space[r][c]=='/' && (dir==1||dir==3)) dir = (dir+3)%4;
            else if(space[r][c]=='\\' && (dir==1||dir==3)) dir = (dir+1)%4;
            else if(space[r][c]=='\\' && (dir==0||dir==2)) dir = (dir+3)%4;
            cnt++;
        } while(r>=1 && r<=n && c>=1 && c<=n);

        System.out.println(cnt-1);
    }
}