글 읽기 - 한번씩 오셔서 도움 부탁드립니다!!

tprjs456 2년 전 0

원래 풀었던 방법에서 반례를 확인하고 반례까지 해결시켰는데 어느 부분에서 오류가 발생하는지 찾지못했습니다.

또 다른 반례가 있는건지 아니면 제가 생각하지 못한 부분이 있는지 궁금합니다 도움 부탁드립니다!

#include<iostream>
#include<cmath>
#include<vector>
#include<string>

#define endl "\n"

using namespace std;

int N;
char map[55][55];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < N; j++) {
			map[i][j] = str[j];
		}
	}
}
int color[55][55];
void Print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << color[i][j];
		}cout << endl;
	}
}
int dix[7] = { -1,-1,0,1, 1, 0, -1 };
int diy[7] = { 0,  1,1,0,-1,-1,0 };
int result = 0;


void Color(int x, int y) {
	for (int i = 0; i < 6; i++) {
		int dx = x + dix[i];
		int dy = y + diy[i];

		if ((dx > 0 && dx < N && dy>0 && dy < N)) {
			if (map[dx][dy] == 'X') { result = 2; }
		}
	}
}

void Find(int x, int y) {
	bool chk = 0;
	for (int i = 0; i < 6; i++) {
		int dx = x + dix[i];
		int dy = y + diy[i];
		int ddx = x + dix[i + 1];
		int ddy = y + diy[i + 1];
		if ((dx >= 0 && dx < N && dy>=0 && dy < N) && (ddx >= 0 && ddx < N && ddy>=0 && ddy <= N)) {
			if (map[dx][dy] == 'X' && map[ddx][ddy] == 'X') {		//삼각형 모형을 만드는 조건
				cout << 3; exit(0);
			}
		}
		if ((dx >= 0 && dx <= N && dy>=0 && dy <= N)) {
			if (map[dx][dy] == 'X') {
				result = 2; 
				if (color[dx][dy] == 0) {
					if (color[x][y] == 1) { color[dx][dy] = 2; }
					else if (color[x][y] == 2) { color[dx][dy] = 1; }
				}
				else {
					if (color[dx][dy] == color[x][y]) {
						result = 3;
					}
				}
			}
		}
	}
}

void Solve() {
	bool chk=false;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 'X') {
				result = 1;
				if (chk == false) { color[i][j] = 1; chk = true; }
				Find(i, j);

			}
		}
	}
	//Print();
	cout << result;
}


int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	Input();
	Solve();
}

tprjs456 2년 전 0

자답입니다!

너무 답답한 나머지 좀 더 생각하지 못하고 질문을 올렸던 것 같습니다.

문제점이 많았습니다.

result 값에 계속 고정된 값을 넣어주었습니다. 그래서 그전까지의 과정에서 2를 찾아내도 1로 끝나면 1이 찍혔습니다.

그리고 DFS를 사용하지 않고 그냥 맵에서 X 를 찾아서 풀어내려가다보니 이어지는 곳을 따라 계속 가지못하고 따로따로 다른 곳에서 서로 같은 값에 색을 칠하려고 중복이 되서 result 의 최솟값을 찾아내지 못했습니다.

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

문제

문제

출처

ICPC

한번씩 오셔서 도움 부탁드립니다!!

tprjs456 2년 전 0

tprjs456 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말