Inflearn Community Q&A
asked
4-H 질문 있습니다 (코드 리뷰)
Resolved
Written on
·
27
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
http://boj.kr/b3eb3e9c71734920b90744bbb7a53927
안녕하세요,
문제의 벽이 1 2 4 8로 구성된 것을 보고 비트마스킹으로 벽을 허물 수 있지 않을까? 해서 생각해본 코드입니다.
comp까지는 미처 풀때 생각하지 못하고
(그리고 comp 사이즈가 2504인 것은 모든 칸이 벽으로 차있는 경우를 상정하여 50*50 + 알파로 하신 게 맞나요?)
한번 자연적으로 주어진 상태에서 문제에서 요구하는 1번, 2번 답을 구한다
모든 벽을 한번씩 허물어본다 (이때 solve 로직 전후로 비트 조작)
그래서 3번 답을 구한다
이런 로직으로 생각을 해봤는데 선생님의 답과 비교해봤을 때 조금 더 1차원적이었던 것 같습니다.
실제 이 문제가 코테에 나온다 가정했을 때도 아마 제 풀이를 일단 시도해봤을 것 같은데, 적절한지 여부가 궁금합니다.
항상 감사합니다!
Answer 2
0
안녕하세요 세림님 ㅎㅎ
코테때 이렇게 생각하시고 하는거 무방합니다.
벽허물기 이부분이 게 조금 아쉽긴하죠 너무 많은 중복 계산이 생기긴하지만 괜찮습니다.
나머지 코드 너무 좋네요 ㅎㅎ
(그리고 comp 사이즈가 2504인 것은 모든 칸이 벽으로 차있는 경우를 상정하여 50*50 + 알파로 하신 게 맞나요?)
네 맞습니다. 최대크기 + 4 이렇게 하는게 좋아요
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 예세림님 질문해 주셔서 감사합니다.
질문하신 문제의 핵심은 성곽의 벽을 비트마스킹을 통해 다루고, 각 벽을 허물어 최대 영역을 구하는 문제입니다. 이 문제는 다양한 접근이 가능하지만, 비트마스킹을 사용하여 벽의 상태를 효과적으로 기록하고 활용할 수 있습니다.
문제 접근 방법
초기 상태 파악: 문제 조건에 따라 초기 성곽 상태를 확인하고 영역을 구분합니다. 비트마스킹을 이용해 벽의 정보를 저장하고, DFS나 BFS를 통해 각 연결된 영역의 크기를 계산합니다.
모든 벽 고려: 각 벽을 하나씩 허물어보고 그 결과를 기록합니다. 이를 통해 가장 큰 영역을 형성하는 벽의 조합을 찾습니다.
최대 영역 계산: 벽을 허물고 난 후의 최대 영역 크기를 계산합니다. 이 때, 각 벽의 방향과 상태를 비트마스크로 관리하여 쉽게 접근할 수 있도록 합니다.
비트마스킹의 활용
- 벽의 상태 기록: 1, 2, 4, 8의 값은 각각 동쪽, 북쪽, 서쪽, 남쪽 벽의 유무를 나타냅니다. 각 칸의 벽 상태를 비트 연산으로 쉽게 조작할 수 있습니다.
- 벽 허물기: 각 칸에서 특정 방향의 벽을 허물고 새로운 상태에서의 영역 크기를 시험할 수 있습니다.
참고할 수 있는 자료
비슷한 문제를 다룬 다른 게시물도 참고하시기 바랍니다. 빠르게 문제 해결을 위한 전략을 세우는데 도움이 될 수 있습니다.
- 4-H_2234_성곽 질문에 대한 해결 – 큰돌 강사님께서 비슷한 이론적 논의와 코드를 제공한 사례입니다.
해당 링크에서는 벽을 허물었을 때의 영역 변화나 비트마스킹의 활용법에 대해 자세히 설명하고 있으니 이를 참조하여 보완해 보시면 좋겠습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.