leeyh2006   4년 전

높이가 6이라고 가정하면 6이하인 안전 영역은 찾았는데 (예 {0,1},{2,1},{3,0},{4,0},{4,1} ,{4,4} )

 여기서 어떻게 갯수를 카운트 해야 될 지 도저히 방법이 떠오르지가 않아서요

안전 영역을 true라고 놓고 인접한 부분이 모두다 false 일 경우 큐에 넣는 식으로해서 다 찾으면 깊이를 카운트 하고 싶은데 .. 조건을 어떻게 놔야 될지 모르겠네요 도와주시면 감사합니다 ! 


plzrun   4년 전

일단 저랑 똑같이 문제 이해를 잘못하신거 같아요 ㅋㅋㅋ

53번째줄 보니까 6이하인 것들만 어떻게 하시는데.. 그게 아니라 0부터 100까지 다 해봐야 하는 문제거든요.


아무튼 그래서 질문 올라온거 보고 풀어봤는데,

저도 자꾸 틀렸다고 뜨길래 봤더니 인접한 영역이 false인거.. 그니까

지금 예제에선 왼쪽 아래에 7개 붙어있는 흰색깔 영역들 중에 양 끝에 있는 2개 영역빼서 5개라고 생각하고 계신거 아닌가요??


근데 그게 아니라 높이를 0부터 100까지 다 해봤을 때

흰색 영역이 인접해 있는거를 전부 한덩어리로 생각하고

그 덩어리의 개수가 최대가 될때, 그 최대값을 출력하는 게 문제에요.


만약 이런 내용에 해당된게 아니라면 아래 글은 무시해주세요~


======================================아래는 위와 같이 문제를 착각했을 때 풀이 법==========================================

일단 그래도 생각하신 인접한 애들을 푸는 방법을 설명해보자면,

bfs돌려서 일단 해당 높이보다 작은애들을 전부 체크해주고

그럼 체크 안된애들만 dfs를 돌려요.


dfs탐색이 한번 들어갈때마다 plus++; 해주시고,

인접한 정점중 뚫려있는 곳이 1개 이하이면 minus++;해줘서

나중에 dfs 다 돌고 나오면 mx = max(mx, plus-minus); 해서 저장해주면 돼요.



물론 이게 문제가 아니니까.. (완전 엉뚱한 문제를 풀었죠...) ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이 문제는 그냥 덩어리를 세주세요. 이건 아실거 같아서 다시 물어보시면 글 남겨 드릴게요.




  • //주의 !! 아래 코드는 이 문제의 정답이 아닙니다.

leeyh2006   4년 전

@plzrun 아 53번째 있는 줄은 그냥 6은 높이를 6이라고 가정만 한 경우 6의 경우만 찾아서 ..ㅋㅋ 나중에 다 처리하고 안전영역이 최대인 경우를 찾아서 출력 해줄려고 했었거든요~ 근데 말씀하신대로  7개가 붙어있는 영역을 하나로 보려고 조건문 처리를 해주려고 하는데 그 부분을 어떻게 해야 할지 도저히 생각이 안나더라구요 ㅠㅠ

plzrun   4년 전

아하 그러면

일단 안전한영역에 해당하는 애들을 bfs든 dfs든 돌려서 다 구했잖아요?

그럼 (x,y)가 안전한 영역이라고 할때 safe[x][y]=true; 라고 할께요.

safe배열값이 true인 애들로 부터 다시 dfs를 돌려요. (bfs돌려도 상관없죠)

그렇게 갈수있는곳까지 다 가고 나면 +1해주면 돼요.

그리고 아직 safe값이 true인 애들을 그런식으로 다 dfs돌아주면

덩어리 개수를 셀 수 있어요 ㅎ

leeyh2006   4년 전

@plzrun 그러면 안전한 영역에 대해서 인접한 부분의 대한 처리는 안해줘도 되는건가요 ~?

plzrun   4년 전

인접한 부분을 따로 처리한다는게 무슨말인지 잘 모르겠네용..

그니까 안전한 영역 그룹들이 있잖아요?

그중에 하나를 택해서 거기서부터 dfs든 bfs든 돌리면 인접한 애들은 다 방문하잖아요?

그럼 중간에 물에 잠긴부분 때문에 아직 탐색하지 못한 부분이 남아있죠?

그건 그럼 안전한 영역중에 아직 그래프 탐색(dfs든 bfs든..)을 하지 않은 부분이면 다시 거기서부터 탐색을 해요.

이런식으로 해서 탐색을 시도한 횟수가 가장 많은 경우가 답이 되겠죠?



코드 첨부할게요~

leeyh2006   4년 전

@plzrun 아 이런식으로 하는 거구나 .. 자꾸 저는 bfs 함수 안에서 다 해결해서 결과 값을 얻으려고 했던 것 같네요 ㅠㅠ 아직 bfs나dfs에 대한 개념이 확실하게 안박혀 있는 것 같네요 다시 공부해야 겠어요~ 답변 감사합니다 !

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