방속의 거울


작성일 : 2017-02-07 13:55:05
조회수 : 865


본문



최대 길이가 1,000 인 정사각형에 1*1 크기로 공간을 나누고, 특정 위치에는 거울을 배치한 상태의 방이 있다.

가장 왼쪽 위에서 레이저를 쏘았을 때, 빛이 밖으로 빠져나가기까지 반사된 거울의 개수를 구하는 문제이다.


거울은 위의 그림과 같이 2가지 방향으로 배치되어 있다. 배치된 거울의 상태와, 빛이 들어온 방향을 case로 나누어 다음 반사되는 방향을 계산할 수 있다. 빛의 이동은 1칸 단위로 진행하면 되며, 한 번 반사된 거울은 중복해서 세어주면 안되므로 별도의 체크를 필요로 한다.

#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char room[1000][1000];
bool visit[1000][1000];
//1(우상->좌하 ->:위로 <-:아래 ↑:오른↓:왼)
//2(좌상->우하 ->:아래 <-:위 ↑:왼↓:오른)
int main()
{
    int t;

    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        //->:0,<-:1,위:2,아래:3
        int n, x = 0, y = 0, dir = 0, ans = 0;
        memset(visit, 0, 1000000);
        cin >> n;
        for (int j = 0; j < n; j++)
                scanf("%s", &room[j]);
        while (x >= 0 && y >= 0 && x<n && y<n)
        {
            if (room[x][y] == '1')
            {
                if(!visit[x][y])ans++;
                visit[x][y] = true;
                if (dir == 0)dir = 2;
                else if (dir == 1)dir = 3;
                else if (dir == 2)dir = 0;
                else dir = 1;
            }
            else if (room[x][y] == '2')
            {
                if(!visit[x][y])ans++;
                visit[x][y] = true;
                if (dir == 0)dir = 3;
                else if (dir == 1)dir = 2;
                else if (dir == 2)dir = 1;
                else dir = 0;
            }
            if (dir == 0)y++;
            else if (dir == 1)y--;
            else if (dir == 2)x--;
            else x++;
        }
        cout << "Case #" << i << "\n" << ans << "\n";
    }
}

방속의 거울 - 알고리즘닷컴
여기서는 https://codeground.org 풀이를 포스팅합니다.

3 개의 글