글 읽기 - 도움이 필요합니다!!!

vo0oa 3년 전 0

질문검색에 있는 거의 모든 테스트케이스를 시도해보면서 맞도록 많이 고쳤는데도 제출하면 결국 틀리네요.

제가 짠 방법으로는 가망이 없고, dfs 같은 방법으로 다시 짜야하는 걸까요?

반례나, 어떻게 개선하면 좋을지? 도움을 주시면 감사하겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> p;
int n, m, arr[10][10], ans, chk[10][10];
vector<p> dir = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
vector<pair<int, p>> camera;

int cntDir(int x, int y, int d) {
	int ret = 0;
	int nx = x, ny = y;
	while (1) {
		nx += dir[d].first, ny += dir[d].second;
		if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == 6) break;
		if (arr[nx][ny] || chk[nx][ny]) continue; // 카메라이거나 방문했던 곳이면 continue;
		ret++;
	}
	return ret;
}

void check(int x, int y, int d) {
	chk[x][y] = 1;
	int nx = x, ny = y;
	while (1) {
		nx += dir[d].first, ny += dir[d].second;
		if (nx < 0 || ny < 0 || nx >= n || ny >= m || arr[nx][ny] == 6) break;
		if (arr[nx][ny] || chk[nx][ny]) continue;
		chk[nx][ny] = 1;
	}
}

void go() {
	for (auto front : camera) {
		int num = front.first, x = front.second.first, y = front.second.second;
		int idx = 0, Max = 0; // 카메라 방향, 감시할 수 있는 영역 크기
		// 카메라의 4방향 확인. 6은 벽 0 은 빈 칸
		switch (num){
			case 1:
				for (int i = 0; i < 4; i++) {
					int tmp = cntDir(x, y, i);
					if (Max < tmp) {
						Max = tmp; idx = i;
					}
				}
				check(x, y, idx);
				break;
			case 2:
				for (int i = 0; i < 2; i++) {
					int tmp = cntDir(x, y, (0 + i) % 4) + cntDir(x, y, (2 + i) % 4);
					if (Max < tmp) {
						Max = tmp; idx = i;
					}
				}
				check(x, y, (0 + idx) % 4);
				check(x, y, (2 + idx) % 4);
				break;
			case 3:
				for (int i = 0; i < 4; i++) {
					int tmp = cntDir(x, y, (0 + i) % 4) + cntDir(x, y, (3 + i) % 4);
					if (Max < tmp) {
						Max = tmp; idx = i;
					}
				}
				check(x, y, (0 + idx) % 4);
				check(x, y, (3 + idx) % 4);
				break;
			case 4:
				for (int i = 0; i < 4; i++) {
					int tmp = cntDir(x, y, (0 + i) % 4) + cntDir(x, y, (2 + i) % 4) + cntDir(x, y, (3 + i) % 4);
					if (Max < tmp) {
						Max = tmp; idx = i;
					}
				}
				check(x, y, (0 + idx) % 4);
				check(x, y, (2 + idx) % 4);
				check(x, y, (3 + idx) % 4);
				break;
			case 5:
				check(x, y, 0);
				check(x, y, 1);
				check(x, y, 2);
				check(x, y, 3);
				break;
		}		
	}
}

bool cmp(pair<int, p> a, pair<int, p> b) {
	if (a.second.first == b.second.first)
		if (a.first == b.first)
			return a.second.second > b.second.second;
		else return a.first > b.first;
	return a.second.first > b.second.first;
}

int main() {
	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] >= 1 && arr[i][j] <= 5) {
				camera.push_back({ arr[i][j], { i, j } });
			}
		}
	}

	sort(camera.begin(), camera.end(), cmp);
	go();

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (arr[i][j]) continue;
			else if (!chk[i][j]) ans++;
	// 출력
	printf("%d", ans);

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도움이 필요합니다!!!

vo0oa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말