[SCPC] 12번: 방속의 거울

[SCPC] 12번: 방속의 거울

N 행 N 열로 이루어진 정사각형 격자구조 내에 방들 중에서 몇 개의 방에는 ╱ 또는 ╲ 형태의 대각선으로 45도 기울어진 양면거울이 들어 있다.

거울은 상하좌우에서 오는 빛을 다시 상하좌우 방향의 방으로 직각 반사시킨다. 본 문제에서는 '가장 윗줄에서 가장 왼쪽 방'의 왼쪽에서 레이저 포인터로 빛을 수평(0도)으로 비추었을 때 빛이 거치는 서로 다른 거울 개수를 계산하려고 한다.

예를 들어, 위 그림을 보자.

그림에서는 "①" 방으로 들어온 빛이 6번의 반사를 거친 후 3 ⅹ 3 크기의 격자구조 밖으로 빠져나간다. 그 중 "②" 방에 있는 거울의 경우, 한 거울의 양쪽 면에서 두 번의 반사가 일어난 것이다. 따라서 위의 예에서 빛을 반사한 거울은 5개이다. 이 문제를 해결하는 프로그램을 작성하시오.

메모리 사용 제한

• heap, global, static (총계) : 256MB
• stack : 1MB

입력

입력 파일에는 여러 개의 테스트 케이스가 포함되어 있다. 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T 가 주어지고, 이후 차례로 T 개의 테스트 케이스가 주어진다. (1≤T≤20)

각각의 테스트 케이스 첫 번째 줄에는 정사각형 격자구조의 '한 변의 방 개수'를 나타내는 정수 N 이 주어진다. (1≤N≤1,000)

다음 줄부터는 N 개의 줄이 주어지고, 각 줄마다 N 개의 문자가 주어진다, 각 문자는 { ‘0’, ‘1’ , ‘2’ }에 속하는 문자 중 하나이다.

문자 ‘1’은 우측 상단에서 좌측 하단으로 45도 기울어진 양면거울이 그 방에 있다는 것을 나타내며,

문자 ‘2’는 좌측 상단에서 우측 하단으로 45도 기울어진 양면거울이 그 방에 있다는 것을 나타낸다.

그리고 문자 ‘0’은 거울이 없는 방임을 나타낸다. 각 줄에 들어 있는 문자들 사이에 빈칸(공백)은 없다.

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다.

그 다음 줄에는 정사각형 격자구조 건물의 '맨 위 맨 왼쪽 방'의 왼쪽에서 수평(0도)으로 들어간 빛이 그 건물을 빠져나올 때까지 거치는 서로 다른 거울의 개수를 출력한다.

입출력예

입력

3
2
02
11
3
201
220
210
4
2121
0102
2101
2121

출력

Case #1
3
Case #2
5
Case #3
8

출처

[SCPC 2015 - 1차 예선]

등록자

이프로

풀이

방을 2차원 배열이라고 생각해봅시다. 레이저포인터는 (0, 0)에서 시작하여 거울을 만나지 않으면 오른쪽으로 한 칸 이동합니다. 따라서 초기 레이저포인터는 (1, 0)의 벡터라고 생각해도 될 것 같습니다.

거울은 레이저포인터를 반사시킵니다. 즉, 벡터의 방향을 바꿉니다. 거울의 종류와 벡터에 따른 변화는 다음과 같습니다.

벡터	'1'	'2'
(1,0)	(0,-1)	(0,1)
(0,1)	(-1,0)	(1,0)
(-1,0)	(0,1)	(0,-1)
(0,-1)	(1,0)	(-1,0)

(x,y) 벡터가 '1' 거울을 만났을 때는 (-y,-x), '2' 거울을 만나면 (y,x)가 되는 것을 알 수 있습니다.

거울을 만날 때마다 벡터를 변환해주고, 현재 위치에 벡터를 더해줍니다. 현재 위치가 2차원 배열의 인덱스를 벗어났을 때 레이저가 방을 통과했다고 판단하여 루프를 종료합니다.

거울을 만나면 해당 거울이 처음 접촉하는 거울인지 판단하고, 처음 접촉하는 거울이면 횟수를 셉니다.

#include <vector>
#include <iostream>

using namespace std;

int Answer;

int main(int argc, char** argv) {
  int T; cin >> T;

  int size;
  string row;
  vector<int> count;
  vector<string> room;
  pair<int, int> direction;

  for(auto test_case = 0; test_case  < T; test_case++) {

    Answer = 0;
    direction = make_pair(1, 0);

    cin >> size;
    count = vector<int>(size * size, 0);
    room = vector<string>(size);
    for (auto i=0; i<size; i++) {
      cin >> room[i];
    }

    int x = 0, y = 0, tmp, sign;
    while (1) {
      if (room[y][x] != '0') {

        sign = 1;
        tmp = direction.first;

        if (room[y][x] == '1') {
          sign = -1;
        }

        direction.first = sign * direction.second;
        direction.second = sign * tmp;

        if (count[y * size + x] == 0) {
          count[y * size + x] = 1;
          Answer++;
        }
      }

      x += direction.first;
      y += direction.second;
      if (x < 0 || x >= size || y < 0 || y >= size) {
        break;
      }
    }

    cout << "Case #" << test_case+1 << endl;
    cout << Answer << endl;
  }

  return 0;
}