4-h성곽 문제 dfs 언더플로 오버플로 체크

작성한 질문수 8

1

안녕하세요 lovewrite님 ㅎㅎ

혹시 그 이유가 지도가 무조건 성벽에 둘러싸여져 있어서 그런 것일까요?

>>

예리한 질문이시네요 ㅎㅎ 네 맞습니다. 문제 지문을 보면

대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.

성곽 자체가 벽으로 이미 둘러싸져 있어서 ny, nx가 배열 범위 바깥으로 벗어나는 < 0 인지 > n 인지를 확인할 필요가 없습니다. 어차피 벽으로 둘러쌓여져 있기 때문이죠.

항상 문제에서 주어진 조건을 중심으로 항상 생각해야 합니다.

문제 지문에 따라 문제의 난이도가 하락하는 경우가 많은데요. 예를 들어 치즈문제, 2 - Q 2636 문제가 대표적인데요. 이문제는 바깥에서 dfs를 한번만 돌리는 것을 반복하는 문제인데, 이 문제 자체가 "만약에"

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이러한 지문이 없다면 더 어려워집니다. 사각형모양의 판이 아니라면 치즈가 "없는"부분부터 dfs를 돌려야 하니 해당 부분에 대한 로직이 더 추가가 되어 더 어려워지는 것이죠.

문제 지문을 잘 읽고 그것을 중심으로 로직을 구축하다보면 어떠한 로직이 없어지거나 좀 더 쉽게 짤 수 있게 될 수도 있습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.