[백준 C++] 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번 구멍으로 쏜 빛이 나가는 구멍의 번호를 출력한다.

https://www.acmicpc.net/problem/2344

풀이

!!! 백준사이트는 scanf("%d", bool) 안됨
숫자는 숫자대로받아서 따로 bool 변수에 넣어줘야함

구현문제입니다.

  1. 빛을 쏘는 함수
  2. 빛을 진행시키는 함수
  3. 빛이 나온위치를 파악하는 함수

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, m;
bool **mirror;
int dx[4] = {0, -1, 0, 1}; //우 상 좌 하
int dy[4] = {1, 0, -1, 0}; //

int beam(int x, int y, int dir);
int findNumber(int x, int y);
void init();
void func();

void func() {
	for (int k = 0; k < n; k++) { // →
		printf("%d ", beam(k, 0, 0));
	}
	for (int k = 0; k < m; k++) { // ↑
		printf("%d ", beam(n - 1, k, 1));
	}
	for (int k = 0; k < n; k++) { // ←
		printf("%d ", beam(n - 1 - k, m - 1, 2));
	}
	for (int k = 0; k < m; k++) { // ↓
		printf("%d ", beam(0, m - 1 - k, 3));
	}
}

void init() {
	scanf("%d%d", &n, &m);
	mirror = new bool* [n];
	for (int i = 0; i < n; i++) {
		mirror[i] = new bool[m];
		for (int j = 0, _; j < m; j++) {
			scanf("%d", &_);
			if (_ == 0)
				mirror[i][j] = 0;
			else
				mirror[i][j] = 1;
		}
	}

}

int findNumber(int x, int y) {
	if (y < 0) return x + 1;
	if (x == n) return n + y + 1;
	if (y == m) return n + m + (n - x);
	if (x < 0) return 2 * n + m + (m - y);
}

//x,y에서 dir방향으로 빛이 출발 (출발위치도 거울영향받음)
int beam(int x, int y, int dir) {
	if (x < 0 || y < 0 || x == n || y == m)
		return findNumber(x, y);

	if (mirror[x][y]) {
		if (dir == 0) return beam(x + dx[dir + 1], y + dy[dir + 1], dir + 1);
		if (dir == 1) return beam(x + dx[dir - 1], y + dy[dir - 1], dir - 1);
		if (dir == 2) return beam(x + dx[dir + 1], y + dy[dir + 1], dir + 1);
		if (dir == 3) return beam(x + dx[dir - 1], y + dy[dir - 1], dir - 1);
	}
	else {
		return beam(x + dx[dir], y + dy[dir], dir);
	}
}


int main(void) {
	init();
	func();

	return 0;
}

좋은 웹페이지 즐겨찾기