[코드 그라운드] 방속의 거울 [SCPC 예선 문제] [미해결]

문제

N 행 N 열로 이루어진 정사각형 격자구조 내에 방들 중에서
몇 개의 방에는 ╱ 또는 ╲ 형태의 대각선으로 45도 기울어진 양면거울이 들어 있다.
거울은 상하좌우에서 오는 빛을 다시 상하좌우 방향의 방으로 직각 반사시킨다.
본 문제에서는 '가장 윗줄에서 가장 왼쪽 방'의 왼쪽에서 레이저 포인터로 빛을 수평(0도)으로 비추었을 때
빛이 거치는 서로 다른 거울 개수를 계산하려고 한다.
 

 

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


- 제한 시간 : 전체 테스트 케이스는 20개 이하이며, 전체 수행 시간은 1초 이내 (Java 2초 이내) 
    제한 시간을 초과하면 제출한 소스코드의 프로그램이 즉시 종료되며,
    그때까지 수행한 결과에서 테스트 케이스를 1개 그룹 이상 통과하였더라도 점수는 0점이 됩니다.
    그러나, 제한 시간을 초과하더라도 테스트 케이스를 1개 그룹 이상 통과하였다면 '부분 점수(0< 점수< 만점)'를 받을 수 있으며,
    이를 위해서는, C / C++ 에서 "printf 함수" 사용할 경우, 프로그램 시작부분에서 "setbuf(stdout, NULL);"를 한번만 사용하십시오.
    C++에서는 "setbuf(stdout, NULL);"와 "printf 함수" 대신 "cout"를 사용하고, Java에서는 "System.out.printIn"을 사용하시면,
    제한 시간을 초과하더라도 '부분 점수'를 받을 수 있습니다.                                     ※ 언어별 기본 제공 소스코드 내용 참고
    만약, 제한 시간을 초과하지 않았는데도 '부분 점수'를 받았다면, 일부 테스트 케이스를 통과하지 못한 경우 입니다.

- 메모리 사용 제한 : heap, global, static 총계 256MB, stack 1MB
- 제출 제한 : 최대 10회 (제출 횟수를 반영하여 순위 결정 → 동점자의 경우 제출 횟수가 적은 사람에게 높은 순위 부여)
- 점수 : 최대 7회 제출하여 취득한 각각의 점수 중에서 최대 점수

메모리 사용 제한

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

입력

입력 파일에는 여러 개의 테스트 케이스가 포함되어 있다.
파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T 가 주어지고,
이후 차례로 TT 개의 테스트 케이스가 주어진다. ( 1≤T≤201≤T≤20) 
각각의 테스트 케이스 첫 번째 줄에는 정사각형 격자구조의 '한 변의 방 개수'를 나타내는 정수 N 이 주어진다. ( 1≤N≤1,0001≤N≤1,000 ) 
다음 줄부터는 NN 개의 줄이 주어지고, 각 줄마다 NN 개의 문자가 주어진다, 각 문자는 { ‘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

푸는 TIP

구조체 room에 거울의 데이터를 저장하는 mirror, 이미 지나쳐 갔는지 확인하는 bool형 been 변수를 만들어 놓는다.

소스코드

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
#pragma warning(disable : 4996) //비주얼스튜디오 scanf 오류 무시
int Answer;
typedef struct room {
	int mirror; //거울 데이터 저장
	bool been; //이미 갔는지 확인
}Room;
typedef struct location {
	int x;
	int y;
	char dir; //진행하려는 방향
	int count;
}Loc;
void myFlush(void) {
	while (getchar() != '\n')
		getchar();
}

Room** build_room(Room** room, int N) {
	int i = 0, j = 0, temp = 0;
	room = (Room**)malloc(sizeof(Room) * N);
	for (i = 0; i < N; i++) {
		room[i] = (Room*)malloc(sizeof(Room) * N);
	}
	for (i = 0; i < N; i++) {
		myFlush();
		for (j = 0; j < N; j++) {
			scanf("%c", &temp);
			room[j][i].mirror = temp-48; //%c로 받았으니 숫자가 아닌 문자로 인식되서 '0'을 받음으로 아스키 코드만큼 빼기
			if (temp == 0) {
				room[j][i].been = 0;
			}
			else {
				room[j][i].been = 1;
			}
		}
	}
	return room;
}
void loc_reset(Loc *loc) {
	loc->x = 0;
	loc->y = 0;
	loc->dir = 'R';
	loc->count = 0;
}
void make_dir_0(Loc * loc) {
	switch (loc->dir) {
	case 'L':
		loc->x--;
		break;
	case 'R':
		loc->x++;
		break;
	case 'U':
		loc->y--;
		break;
	case 'D':
		loc->y++;
		break;
	}
}
void make_dir_1(Loc * loc) {
	switch (loc->dir) {
	case 'L':
		loc->y++;
		loc->dir = 'D';
		break;
	case 'R':
		loc->y--;
		loc->dir = 'U';
		break;
	case 'U':
		loc->x++;
		loc->dir = 'R';
		break;
	case 'D':
		loc->x--;
		loc->dir = 'L';
		break;
	}
}
void make_dir_2(Loc * loc) {
	switch (loc->dir) {
	case 'L':
		loc->y--;
		loc->dir = 'U';
		break;
	case 'R':
		loc->y++;
		loc->dir = 'D';
		break;
	case 'U':
		loc->x--;
		loc->dir = 'L';
		break;
	case 'D':
		loc->x++;
		loc->dir = 'R';
		break;
	}
}
void endless_move(Room** room, Loc * loc, int N) {
	int check_mirror;
	while ((loc->x < N) && (loc->x >= 0) && (loc->y < N) && (loc->y >= 0)) {
		check_mirror = room[loc->x][loc->y].mirror;
		if (check_mirror == 0) {
			make_dir_0(loc);
		}
		else if (check_mirror == 1) {
			if (room[loc->x][loc->y].been == true) {
				room[loc->x][loc->y].been = false;
				loc->count++;
			}
			make_dir_1(loc);
		}
		else { //room[x][y]의 mirror 상태가 2인 경우
			if (room[loc->x][loc->y].been == true) {
				room[loc->x][loc->y].been = false;
				loc->count++;
			}
			make_dir_2(loc);
		}
	}
}
void set_free(Room*** room, int N) {
	for (int i = 0; i < N; i++) {
		free(room[i]);
	}
	free(room);
}

int main(void)
{
	int T, test_case;
	setbuf(stdout, NULL);
	Room** room = NULL;
	Loc loc;
	int N = 0;
	scanf("%d", &T);
	for (test_case = 0; test_case < T; test_case++)
	{
		loc_reset(&loc);
		scanf("%d", &N);
		room = build_room(room, N);
		endless_move(room, &loc, N);
		Answer = loc.count;
		printf("Case #%d\n", test_case + 1);
		printf("%d\n", Answer);
		set_free(&room, N);
	}
	return 0;
}

느낀 점

일단 메모리 오버플로우가 발생해서 실패상태이긴 하다.

모든 test case를 통과하긴 했지만 어느 부분이 메모리 초과를 발생하는지는 모르겠다. set_free함수로 malloc으로 메모리 설정해놓은거를 free 해줬지만, 

출처

[SCPC 2015 - 1차 예선]