nugongja   1년 전

하나의 셀에서 시작해서 가로나 세로 방향으로 분기하면서 7칸을 확장하는 방식으로, 이 문제를 BFS만으로 구현하는 게 가능할까요?

7576번 토마토 문제처럼 모든 방향으로 일정한 속도로 퍼지는 구조라면 BFS로 구현하기가 쉬운데,
소문난 칠공주 문제는 각 방향마다 이동 거리나 깊이가 달라질 수 있는 구조라
이런 분기된 경로들이 BFS 안에서 자연스럽게 하나의 연결된 조합으로 고려될 수 있는지 잘 모르겠습니다.

BFS 탐색 구조로도 이런 분기들을 누락 없이 전부 처리할 수 있을까요?

아니면 처음부터 조합을 만들고 BFS는 연결 여부만 확인하는 문제인 걸까요?

조건이 생각보다 까다로워서 단순히 구현이 어려운 건지,
아니면 애초에 BFS만으로는 풀 수 없는 구조인지 모르겠습니다ㅠ

해당 방식으로 어떻게 구현할지 감이 잘 안 잡혀서 코드 없이 질문 먼저 드립니다!

조언이나 아이디어 주시면 정말 감사하겠습니다!

lcr7324   1년 전

시간이 좀 지났지만 늦게나마 답변을 드리자면,

1) 정말정말 잘 구현하면 BFS 혹은 DFS 기반으로 한 점에서 뻗어나가며 분기를 처리하는 코드를 작성할 수 있을지 모르겠는데, 우선 저는 그 방법을 모르고 구현 난이도 또한 상당할 것으로 생각됩니다.

2) 문제의 출제 의도는 뻗어나가며 분기를 처리하는 방식이 아니라, 25개의 자리 중 칠공주가 위치할 자리를 모두 확인해보며 조건에 맞게 구성되어 있는지(연결되어 있는지 등) 확인하는 것을 의도했다고 생각합니다.

pangitwise   1년 전

해당 문제는 폴리오미노 유형의 문제로 충분히 BFS/DFS로 해결할 수 있습니다. 다만 일반적인 격자 그래프에서의 BFS와 달리 현재 깊이까지 방문한 모든 점에서 뻗어나가야 합니다.

khkim6040   11달 전

윗분 말씀대로 조합 없이 그래프 탐색으로 풀 수는 있을 것 같습니다.

다만, 앞으로 방문할 수 있는 인접한 부분을 일반적인 그래프 탐색에서처럼 지금 방문한 점이 아니라 지금까지 방문했던 부분 모두를 고려해야 합니다. 그리고 같은 모양을 중복해서 고려하는 것을 막기 위한 작업(state 비트마스킹)도 필요합니다.

아래는 그렇게 푼 풀이입니다.

https://www.acmicpc.net/source...

+ 이외에도 7개 자리를 이어붙여 만들 수 있는 모든 모양을 사전에 다 만들어놓고 하나씩 맞춰보는 방법도 있을 것 같은데, 개수가 100개가 넘어가는군요. 

참고: https://en.wikipedia.org/wiki/... 

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