글 읽기 - AC는 받았는데 질문있습니다.

minjae200 5년 전 0

dfs함수에서

}
for (int y = 0; y < 5; y++) {
for (int x= 0; x < 5; x++) {
if (!(state & (1 << (y * 5 + x)))) continue;

이부분을 dfs문 호출할때 ( dfs(1, students[i][j] == 'S', 1 << (i * 5 + j)); )

그냥 i,j값을 넘겨주고

이중for문 없애고 그냥 y,x로 받으면 안되나요? 계속 틀렸습니다가 떠서 질문올립니다.

즉

dfs(i, j, 1, students[i][j] == 'S', 1 << (i * 5 + j));

void dfs(int y, int x, ~~~)

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

char students[5][5];
bool check[1 << 25];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int result;

bool checkRange(int y, int x)
{
	if (0 <= y && y < 5 && 0 <= x && x < 5) return true;
	else return false;
}

void dfs(int cnt, int scnt, int state)
{
	check[state] = true;
	if (cnt >= 7) {
		if (scnt >= 4) result++;
		return;
	}
	for (int y = 0; y < 5; y++) {
		for (int  x= 0; x < 5; x++) {
			if (!(state & (1 << (y * 5 + x)))) continue;
			for (int i = 0; i < 4; i++) {
				int next_y = y + dy[i];
				int next_x = x + dx[i];
				if (checkRange(next_y, next_x)) {
					if (state & (1 << (next_y * 5 + next_x))) continue;
					int next_state = state | (1 << (next_y * 5 + next_x));
					if (check[next_state]) continue;
					dfs(cnt + 1, scnt + (students[next_y][next_x] == 'S'), next_state);
				}
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> students[i][j];

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(1, students[i][j] == 'S', 1 << (i * 5 + j));
		}
	}

	cout << result << endl;
	return 0;
}#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

char students[5][5];
bool check[1 << 25];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int result;

bool checkRange(int y, int x)
{
	if (0 <= y && y < 5 && 0 <= x && x < 5) return true;
	else return false;
}

void dfs(int cnt, int scnt, int state)
{
	check[state] = true;
	if (cnt >= 7) {
		if (scnt >= 4) result++;
		return;
	}
    //이 이중 for문 질문
	for (int y = 0; y < 5; y++) {
		for (int  x= 0; x < 5; x++) {
			if (!(state & (1 << (y * 5 + x)))) continue;
			for (int i = 0; i < 4; i++) {
				int next_y = y + dy[i];
				int next_x = x + dx[i];
				if (checkRange(next_y, next_x)) {
					if (state & (1 << (next_y * 5 + next_x))) continue;
					int next_state = state | (1 << (next_y * 5 + next_x));
					if (check[next_state]) continue;
					dfs(cnt + 1, scnt + (students[next_y][next_x] == 'S'), next_state);
				}
			}
		}
	}
}

int main(void)
{
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 5; j++)
			cin >> students[i][j];

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			dfs(1, students[i][j] == 'S', 1 << (i * 5 + j));
		}
	}

	cout << result << endl;
	return 0;
}

seico75 5년 전 0

틀린 소스와 맞은 소스를 같이 올려주셨으면 이해가 쉬었을텐데, 질문하신 내용을 정확히 파악이 어렵네요.

제가 이해한 바로는 dfs 의 인자로 x, y 를 받아서 dfs 내 이중 for문을 제거하고 그 값만 사용하면 안되느냐 인것 같습니다.

81라인 부터를 해석하면

[이미 선택된 모든 x,y 좌표에 대해서] // 81~83 라인

[4방향중 하나로 확장하고 재귀를 돌린다.] // 84~91 라인

이렇게 생각이 되는데, 만일 말씀하신데로 바꾸면...

[앞에서 선택된 위치를 기준으로 ] // 즉, 인자로 받은 x, y를 중심으로

[4방향중 하나로 확장하고 재귀를 돌린다.] // 똑같이..

가 됩니다. 이 경우 아래와 같은 선택되어야 답이 되는 케이스는 카운트 못할 것 같습니다. (즉, 한붓그리기가 안되는 경우)

00100

01110

00100

이유는 [4방향중 하나로 확장하고 재귀를 돌린다.] 부분이 한발씩만 앞으로 가기 때문입니다. (쉽게 설명하기 어렵네요..)

그래서...

[앞에서 선택된 위치를 기준으로 ]

[4방향에 대한 모든 조합에 대해서 재귀를 돌린다.]

가 되어야 하는데.. " 모든 조합에 대해서 재귀를 돌린다. "를 구현하는 것은 많이 복잡할 것 같네요.

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

문제

문제

출처

ICPC

AC는 받았는데 질문있습니다.

minjae200 5년 전 0

seico75 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말