방 속의 거울 (mirror in the room)

> 문제 출처

https://www.codeground.org/practice/

12 SCP_2015_Online Mirror in the Room

 

> 문제 설명

정사각형 크기(N<=1000)의 방에 각 칸에 거울이 주어진다( '0'=없음, '1'=／, '2'=＼)

빛이 제일 위, 왼쪽칸의 왼쪽에서 출발할 때, 몇개의 거울을 지나치는지 구하는 문제.

출처 : codeground.org/practice - Mirror in the Room

 

> 접근 방법

구조체로 거울 하나에 대한 정보(거울의 모양-mode, 방문여부-isVisited)를 정하였고, 클래스 선언으로 방에 대한 정보(크기, 위치별 거울의 모양)을 확인할 수 있게 만들었다.

 

이제 0,0부터 지나친 거울을 컨트롤 하면 되는데, 거울의 모양만으로는 다음 좌표를 알 수가 없다. 그래서 빛의 방향을 이용하여 함께 계산을 해줘야하는데 4방향을 고려하여 if문을 넣기에는 런타임, 코드 가독성의 문제가 생긴다고 생각했다.

 

빛의 진행 방향을 x,y방향으로 나눈 뒤 직접 그려보며 패턴을 찾아보니 다음과 같았다. 

거울이 없을 때(mode=='0')	거울이 '／'모양일 때(mode=='1')	거울이 '＼'모양일 때(mode=='2')
진행방향이 바뀌지 않는다	(dir_x, dir_y) -> (-dir_y, -dir_x)	(dir_x, dir_y) -> (dir_y, dir_x)

따라서 좌표를 pos(y,x)로 나타냈을 때, 거울에 반사되어 가게 되는 좌표는 pos(y+dir_y, x+dir_x)가 될 것이다.

 

pos(y,x)의 값이 방의 좌표 범위[0,N)이 되는 선에서 거울이 있는(mode!='0'), 방문하지 않은(!isVisited) 거울의 수만 세면 결과가 나오게 된다.

 

> CODE

/*
# problem
https://www.codeground.org/practice/
12	SCPC 2015 Online	
Mirror in the Room

#review
https://ssyoon.tistory.com/16
*/
#include <iostream>

using namespace std;

struct Mirror{
    char mode;
    bool isVisited;
    Mirror(char m='0', bool b=false){mode=m; isVisited=b;}
};

class Room{
    private:
        Mirror** mirror;
        int size;
    public:
        Room(int n=1);
        void setMirror();
        int shootLight();
        inline bool isOut(const pair<int,int> p);
};

Room::Room(int n){
    size = n;
    mirror = new Mirror*[n];
    for(int i=0;i<n;i++)
        mirror[i] = new Mirror[n];
}

void Room::setMirror(){
    for(int i=0;i<size;i++){
        string tmp;
        cin >> tmp;
        for(int j=0;j<size;j++){
            mirror[i][j].mode = tmp[j];
        }
    }
}

int Room::shootLight(){
    int res = 0;

    pair<int,int> pos(0,0);
    int dir_x = 1; // Left=-1, Right=1, No=0
    int dir_y = 0; // Up=-1, Down=1, No=0

    while(!isOut(pos)){
        Mirror& m = mirror[pos.first][pos.second];
        printf("position is (%d,%d), Mode is %c\n", pos.first,pos.second, m.mode);

        if(!m.isVisited && m.mode!='0'){
            res++;
            m.isVisited = true;
        }

        if(m.mode == '0'){
            //direction is not change!
        }
        else if(m.mode == '1' ){
            int swap = dir_x;
            dir_x = -dir_y;
            dir_y = -swap;
        }
        else{// m.mode == '2'
            int swap = dir_x;
            dir_x = dir_y;
            dir_y = swap;
        }
        pos.first += dir_y;
        pos.second += dir_x;
    }
    return res;
}

inline bool Room::isOut(const pair<int,int> p){
    if(p.first < 0 || p.first >=size || p.second <0 || p.second >=size){
        printf("It's out of room! (%d,%d)\n",p.first,p.second);
        return true;
    } 
    return false;
}

int Answer;
int main(int argc, char** argv)
{
	int T, test_case;
	cin >> T;
	for(test_case = 0; test_case  < T; test_case++)
	{
        int N;
        scanf("%d",&N);
        Room mirrorRoom(N);
        mirrorRoom.setMirror();
        Answer = mirrorRoom.shootLight();

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

	return 0;//Your program should return 0 on normal termination.
}

---

https://github.com/dongha-yoon/ProgrammingStudy - mirror.cpp