[백준] 2344번 거울

2344번 거울

문제

---

세로 N, 가로 M 크기의 상자가 있다. 이 상자 안에는 몇 개의 거울이 들어 있다. 상자를 위에서 봤을 때, 거울은 한 칸 안에 대각선 모양으로 들어있다고 한다. 또, 상자의 테두리를 따라서 칸마다 구멍이 뚫려 있다. 편의상 구멍은 왼쪽 위에 뚫려있는 것부터 시계 반대 방향으로 1, 2, …, 2N+2M 의 번호가 붙어 있다. 예를 들어 다음과 같은 경우를 보자.

이제 이 상자에 뚫려있는 구멍으로 빛을 쏜다고 생각해보자. 1번 구멍으로 쏠 경우에는 (1, 2)의 위치에 있는 거울에 반사되어 9번 구멍으로 빛이 가게 된다. 또, 2번 구멍으로 빛을 쏠 경우에는 (2, 2)의 위치에 있는 거울과 (1, 2)에 있는 거울에 차례로 반사되어 7번 구멍으로 빛이 나가게 된다.

이와 같이 상자의 모양이 주어졌을 때, 각 구멍으로 쏜 빛이 나가게 되는 구멍을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N, M (1 ≤ N, M ≤ 1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 상자의 모양이 주어진다. 거울이 있는 위치는 1로, 거울이 없는 위치는 0으로 주어진다. 거울은 / 모양으로만 놓일 수 있다고 하자.

출력

---

첫째 줄부터 차례로 1번 구멍으로 쏜 빛이 나가는 구멍의 번호, 2번 구멍으로 쏜 빛이 나가는 구멍의 번호, …, 2N+2M번 구멍으로 쏜 빛이 나가는 구멍의 번호를 출력한다.

---

풀이)

재귀 방법을 이용해 빛이 어떤 구멍으로 나가는 지 확인해준 문제이다.

1. 세로 N, 가로 M인 상자가 있다면 전체 map크기를 아래처럼 생각한다.

   (예시) N = 5, M =4 일경우

맵 크기는 (N+2 =7) * (M+2 = 6)

2. 구멍의 번호를 저장해준다. 

   (이 때, 거울의 위치와 1번 구멍을 햇갈리지 않기 위해 거울 있는 곳은 -1로 바꿔준다)

3. 각 1번 구멍부터 출발해 다른 구멍의 번호(1이상)가 나올 때까지 탐색해준다.

 3.1 거울을 만날 경우 방향을 바꾼 뒤 탐색

(방향은 항상 수직으로 바뀌며, 왼쪽 방향이였을 경우 위쪽 방향으로. 위쪽 방향이었을 경우 오른쪽 방향으로 바뀜.

 아래 그림처럼 바뀜)

 3.2 거울이 아닌 경우는 방향을 그대로 유지한 채 탐색

코드)

#include <stdio.h>
using namespace std;
 
int N, M;
int map[1005][1005];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
int change_dir(int d) {
    if (d == 0) return 3;
    else if (d == 1) return 2;
    else if (d == 2) return 1;
    else return 0;
}
 
int dfs(int y, int x,int dir) {
    int ny = y + dy[dir];
    int nx = x + dx[dir];
    //다른 구멍으로 빛이 빠짐
    if (map[ny][nx] >= 1) return map[ny][nx];
    else {
        //거울을 만나면
        if (map[ny][nx] == -1) return dfs(ny, nx, change_dir(dir));
        else //거울 안만나면 계속 빛 방향 유지
            return dfs(ny, nx, dir);
    }
}
 
int main() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            scanf("%d", &map[i][j]);
            if (map[i][j] == 1) map[i][j] = -1;
        }
    }
    //1. 구멍 번호 채우기
    //왼쪽면, 오른쪽면 구멍 번호
    for (int i = 1; i <= N; i++) {
        map[i][0] = i;
        map[N + 1 - i][M + 1] = N + M + i;
    }
    //아래면, 윗면 구멍 번호
    for (int i = 1; i <= M; i++) {
        map[N + 1][i] = N + i;
        map[0][M + 1 - i] = N * 2 + M + i;
    }
 
    //2. 구멍에서 빛 쏘기
    //1) 왼쪽면 구멍에서
    for (int i = 1; i <= N; i++) {
        printf("%d ", dfs(i, 0, 3));
    }
    //2) 아랫면 구멍에서
    for (int i = 1; i <= M; i++) {
        printf("%d ", dfs(N+1, i, 0));
    }
    //3) 오른쪽면, 빛 방향 : 왼쪽
    for (int i = N; i >= 1; i--) {
        printf("%d ", dfs(i, M+1, 2));
    }
    //4) 위쪽면, 빛 방향 : 아래
    for (int i = M; i >= 1; i--) {
        printf("%d ", dfs(0, i, 1));
    }
    return 0;
}