각 셀마다 인접한 셀을 체크해나가는데
순서상관없이 빨+파+초 3색이 붙어있는 조합을 모두 찾을거임
이런상황에서 찾는 순서에 따라서 손해를 보는 경우가 발생하는데
그림에서 중앙 하단에 파란색이 위, 오른쪽으로 초록색과 붙어있을 때
case 1의 경우에는 정상적으로 2개 조합을 인정하는데
case 2의 경우에는 다른곳에 붙을 초록색을 먼저 탐색해서
2개 조합이 안나오는 문제가 생기는데
뭐를 참고해야 이걸 효율좋게 해결할 수 있을까?
최악은 그냥 이런 상황을 안나오도록 게임을 설계하는거로 생각중
차악은 이런 상황이 나와도 운에 달려있게 하는것
그냥 내가 주로 쓰는 자바스크립트 기준으로 작성해 보면 점 하나를 선택해서 빨,파,초 중 하나가 인접해 있는 부분이 있으면 전부 테이블에 넣음. 이렇게 연결된 셀들을 조합해서 도형이 가장 많이 나오는 결과값을 반환해서 셀 조합을 완성하면 이상적인 결과물이 나올 것 같음.
자바스크립트로 게임 개발함?
ㄴㄴ 앱개발이 주인데 낭만 쫒아 인디 개발도 해보려고
오.. 선 기준으로 경우의수를 수렴해나가는 방법인것같네. 선분 테이블에서 두개를 뽑아서 서로 같은 점을 공유하고 있다면 2차 테이블에 넣는다. 를 반복하면 도형이 만들어지는 모든 경우의 수를 얻을 수 있겠지
리고 이 경우의 수에 포함되어있는 모든 고유한 점의 개수를 구해서 3의 배수가 넘는다면 1개 이상 존재한다는 것. 있는만큼 2차 테이블에서 뽑되, 동일한 점을 포함하지 않는 경우를 찾으면 되겠다. 감사합니다!
셀마다 자기 색깔과 다른 인접한 셀을 모두 받아두게 하고, 검색을 시작하는 셀에서 인접한 셀에다 자신의 색깔을 쏴주고, 받아온색, 자기색과 다른 인접한 셀을 가지고 있으면 거길 되돌려 주면 3색으로 이어진다 아님?
색 종류가 여러개고 특정 색만 담아야 하면, 색깔 찾아내는 부분에 한번 걸러주는 부분 넣어두면 될거같음
dfs로 이걸 구현하고 싶으면 백트래킹을 쓰면 됨 (모든 경우를 확인하기 땜에 저럴일 없음) 효율 따지고 싶으면 걍 bfs 쓰는게 낫다
조합의 가능한 최대 가지수를 찾는 문제로 보이는데 맞ㄹ을까요? BFS 알고리즘으론 구현이 불가능하고, 최대 유량 알고리즘을 잘 응용하면 다항 시간 내 구현이 가능할 것으로 보입니다. 저도 최대 유량 깊게는 공부를 안해서 구체적으로 어떻게 디자인할지는 감이 안잡히네요.
백준에 "컨닝" 문제와 같이 격자판 형태에 최대 유량을 적용시키는 문제들이 몇 있는데, 해설 찾아서 풀어보시는 것도 도움이 되겠습니다.
간략하게 설명하려고 그리드로 해놨는데 사실 그래프형태에 가까워서 도움이 될것같음 .. 애초에 dfs라고 질문을했네? 암튼 확인해보겠음 감사합니다!
최대유량 구현하실 때 그래프랑 그리드는 구현에 큰 차이는 없습니다, 그것보다 최대유량 템플릿에 맞게 모델링하는 과정이 더 어려운것 같아요. 쉬운 개념이 아닐 수 있는데 화이팅하시구, 막히는거 있으면 댓글 달아주세용
최대 가짓수를 찾는거라면 bfs나 dfs나 똑같은 효율이지 않을까요? 포함되지 않아야 할 색들은 애초에 테이블에서 뺴버리고, 인접리스트 형식으로 한다면 규칙이 깨진 탐색은 더 이상 탐색하지않게 조기종료시키는 식으로 하는게 탐색 효율 그나마 좀 올릴 방법일거같은데 나중에 해결하면 여기에 글좀 싸주세용
손해..? 그러니까 서로 겹치지 않는 선에서 저 세개 짝을 maximize하겠다는거지? dfs는 재방문을 하지 않아야해. 재방문하면 더 이상 dfs가 아니야.. 그리디하게 잡으면 답이 안나오므로 dfs풀이는 불가능함
중앙점이 될 수 있는 점들을 모두 모아서.. 후보가 두개인 이분매칭..도 안되는데 서로 겹치잖아 이게 다항 시간내로 되나?
bfs 쓰세요