틀린 소스와 맞은 소스를 같이 올려주셨으면 이해가 쉬었을텐데, 질문하신 내용을 정확히 파악이 어렵네요.
제가 이해한 바로는 dfs 의 인자로 x, y 를 받아서 dfs 내 이중 for문을 제거하고 그 값만 사용하면 안되느냐 인것 같습니다.
81라인 부터를 해석하면
[이미 선택된 모든 x,y 좌표에 대해서] // 81~83 라인
[4방향중 하나로 확장하고 재귀를 돌린다.] // 84~91 라인
이렇게 생각이 되는데, 만일 말씀하신데로 바꾸면...
[앞에서 선택된 위치를 기준으로 ] // 즉, 인자로 받은 x, y를 중심으로
[4방향중 하나로 확장하고 재귀를 돌린다.] // 똑같이..
가 됩니다. 이 경우 아래와 같은 선택되어야 답이 되는 케이스는 카운트 못할 것 같습니다. (즉, 한붓그리기가 안되는 경우)
00100
01110
00100
00100
00100
이유는 [4방향중 하나로 확장하고 재귀를 돌린다.] 부분이 한발씩만 앞으로 가기 때문입니다. (쉽게 설명하기 어렵네요..)
그래서...
[앞에서 선택된 위치를 기준으로 ]
[4방향에 대한 모든 조합에 대해서 재귀를 돌린다.]
가 되어야 하는데.. " 모든 조합에 대해서 재귀를 돌린다. "를 구현하는 것은 많이 복잡할 것 같네요.
minjae200 5년 전
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, ~~~)