글 읽기 - 1018 질문 입니다. 답변주시면 감사하겠습니다.

byunghoonpark 5년 전 0

게시판에 있는 예제 및 댓글로 달린 예제를 실행해봤는데 전부 옳은 답이 출력 됩니다.

틀린 부분 가르쳐주시면 감사하겠습니다!

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>

using namespace std;

char map[50][50];
char re_map[50][50];
int visit[50][50];
int n, m;
int ret = 2147483647;
int dx[2] = {0,1};
int dy[2] = {1,0};

void func() {
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			map[i][j] = re_map[i][j];
	memset(visit, 0, sizeof(visit));
}

void bfs(int x, int y) {

	func();

	int ans = 0;
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		int qsize = q.size();
		for (int i = 0; i < qsize; i++) {
			int tx = q.front().first;
			int ty = q.front().second;
			q.pop();
			if (map[tx][ty] == 'W') {  
				for (int i = 0; i < 2; i++) {
					int tmpx = tx + dx[i];
					int tmpy = ty + dy[i];
					if (i == 0) { // 오
						if (tmpy > y + 7)
							continue;
						if (map[tmpx][tmpy] == 'B' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							q.push(make_pair(tmpx, tmpy));
						}
						else if (map[tmpx][tmpy] == 'W' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							map[tmpx][tmpy] = 'B';
							q.push(make_pair(tmpx, tmpy));
							ans++;
						}
					}
					else if (i==1) { // 아래 
						if (tmpx > x+7)
							continue;
						if (map[tmpx][tmpy] == 'B' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							q.push(make_pair(tmpx, tmpy));
						}
						else if (map[tmpx][tmpy] == 'W' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							map[tmpx][tmpy] = 'B';
							q.push(make_pair(tmpx, tmpy));
							ans++;
						}
					}
				}
			}
			else if (map[tx][ty] == 'B') {
				for (int i = 0; i < 2; i++) {
					int tmpx = tx + dx[i];
					int tmpy = ty + dy[i];
					if (i == 0) { // 오
						if (tmpy > y+7)
							continue;
						if (map[tmpx][tmpy] == 'W' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							q.push(make_pair(tmpx, tmpy));
						}
						else if (map[tmpx][tmpy] == 'B' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							map[tmpx][tmpy] = 'W';
							q.push(make_pair(tmpx, tmpy));
							ans++;
						}
					}
					else if (i == 1) { // 아래 
						if (tmpx > x+7)
							continue;
						if (map[tmpx][tmpy] == 'W' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							q.push(make_pair(tmpx, tmpy));
						}
						else if (map[tmpx][tmpy] == 'B' && !visit[tmpx][tmpy]) {
							visit[tmpx][tmpy] = 1;
							map[tmpx][tmpy] = 'W';
							q.push(make_pair(tmpx, tmpy));
							ans++;
						}
					}
				}
			}
		}
	}
	if (ans == 63)
		ans = 1;
	ret = min(ret, ans);
}

int main(void) {
	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < m; j++) 
			cin >> re_map[i][j];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (i + 7 < n && j + 7 < m) {
				visit[i][j] = 1;
				bfs(i, j);
			}
		}
	}
	printf("%d\n", ret);
	return 0;
}

evenharder 5년 전 0

bfs 함수의 맨 마지막에서 ret = std::min({ret, ans, 64-ans});가 되어야 합니다.

예시로 밑의 답이 2가 나와야 합니다.

8 8
BBWBWBWB
BWBWBWBW
WBWBWBWB
BWBBBWBW
WBWBWBWB
BWBWBWBW
WBWBWBWB
BWBWBWBW

byunghoonpark 5년 전 0

감사합니다!

ljm1923 5년 전 2

혹시나해서 쉽게 구하는 방법한번 올려드릴게요!

방금 풀이한 내용인데 도움이 되실수도 있을 것 같습니다.

#include <iostream>
using namespace std;

/*
체스판다시칠하기의 풀이전략 19.03.05
최초에는 매 위치에 대하여 다음에 나와야하는 녀석이 누군지 일일이 구하는 방법을 고안하였다. 
하지만 그 방법은 스스로가 머리가 복잡해지는 문제를 야기하였고
그러다가 갑작스레 떠오른 풀이방법은 ans_B와 ans_W에 대한 배열을 만드는 방법에 대한 것이다.
그렇게 ans_B와 ans_W 배열을 선언하고 0,0부터 시작하여 8x8배열을 만드는것이 가능한 위치마다 탐색을 하여
그 위치에서 체스판이 만들어지는지에 대한 여부를 조사하도록 하였다.
이때 한가시 실수는 ans들에 대한 index는 map의 인덱스와 다르다는 것을 간과하였다는 점이다.
그렇기 때문에 x_i와 y_i를 따로 배정을 하여 인덱스접근을 다르게 하였다.
또한 1부터의 접근이 잘못되었다는 생각을 바탕으로 0으로 인덱스시작을 바꾸었는데,
생각해보면 그냥 ans에 대한 인덱스 접근이 잘못되었기 때문에 발생한 문제일 것이다.

*/

char map[51][51];

// 왼쪽 위가 B로 시작할 경우
char ans_B[8][8] = { {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
};

// 왼쪽 위가 W로 시작할 경우
char ans_W[8][8] = { {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
					 {'W','B','W','B','W','B','W','B'},
					 {'B','W','B','W','B','W','B','W'},
};

int N, M;
int min_n = 999;
int cnt_B, cnt_W;
int ans;

void find_mini(int x, int y) {
	
	cnt_B = 0, cnt_W = 0;
    
	int y_i = 0;
	for (int i = y; i < y + 8; i++) {
		int x_i = 0;
		for (int j = x; j < x + 8; j++, x_i++) {
			
			if (map[i][j] != ans_B[y_i][x_i]) cnt_B++;	// map이 왼쪽위가 B인 체스판의 i,j위치와 같지않다면 cnt_B를 ++ 시킨다.
			if (map[i][j] != ans_W[y_i][x_i]) cnt_W++;  // map이 왼쪽위가 W인 체스판의 i,j위치와 같지않다면 cnt_W를 ++ 시킨다.
		}
		y_i++;
	}
    
    // 왼쪽위가 B일 case가 W일때보다 바꿀값이 적다면 B
	if (cnt_B < cnt_W) ans = cnt_B;
	else ans = cnt_W; // 아니라면 W
    
	if (ans < min_n) min_n = ans;  //ans가 min_n보다 작다면 min_n값 업데이트

}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
    
    // 맵 넣기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
    // 각 위치에 대하여 체스판 만들기
	for (int i = 0; i <= N - 8; i++) {
		for (int j = 0; j <= M - 8; j++) {
			find_mini(j,i);
		}
	}

    // min 값 출력
	cout << min_n << endl;

	return 0;
}

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

문제

문제

출처

ICPC

1018 질문 입니다. 답변주시면 감사하겠습니다.

byunghoonpark 5년 전 0

evenharder 5년 전 0

byunghoonpark 5년 전 0

ljm1923 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말