최근 풀이 241108

: bfs + 비트마스킹 + 구현

• 주의할 부분
  : 아래와 오른쪽 원소를 더하는 부분이기 때문에 2중 포문의 범위를 아예 이렇게 설정했다.
  

-> 위 코드의 잘못된 부분
: 77 사이즈라고 해보자. 그러면 66만큼만 확인을 하게 되는데.
0 ~ 5까지만 확인한다. 전체 원소는 y : 0 ~ 6 / x : 0 ~ 6 인데
범위를 전부 순회하지 못하는 경우가 발생한다.

• 오른쪽만 처리하려고 했는데. 이렇게 하면 아래쪽 계산하는 부분에도 영향을 미친다.
  아래쪽 보호하기 위해 작성했는데. 오른쪽 합치는 계산에도 영향을 미친다...

• 예단해서 작성하지 말자.
  : 그냥 for문 돌리게 한 후 , 오른쪽 확인하는 부분만 넘어가지 않게 하면 되는 거자나 .
  그리고 추가적으로 위쪽으로 넘어가는 부분만 막아주면 된다.

---

개선해야 할 부분 : 240129

• 이런식으로 만들려고 함.
  

• 그런데 이렇게 하면서 bfs 내부에서도 매번 이렇게 또 타입을 만들어야 함.
  -> 메모리 낭비다.

https://www.acmicpc.net/submit/2234/72536771

• 이렇게 생각할 수 있음.
  : bfs에 진입할때, 그냥 외부에서 들어오는 카운트 값으로 번호 설정한 후,
  

• 하나의 배열을 만들어서 arr[cnt] = 총 bfs 큐 돌린 카운팅 기록하자.

• 마지막에 3번째 답을 구할 때, 인접한 정점 중 동일하지 않은 정점끼리 합을 구할건데,
  여기서 arr[cnt] 의 값고 와 visited[][] 의 값을 비교해서 처리가 가능함.

• 위의 예시대로 하면, arr[] = { 0,9,3,8,6 } 이 되겠지? 이거랑 visited[][]
  비교 하면 됨.
  

-> 이렇게 비교하자.

---

그리고 마지막으로 3번째 답안 구할 때, 나는 상하좌우로 비교했는데, 이렇게 할 경우, 33 퍼센트에서 틀림
-> 시간 복잡도 증가할 것으로 보임.

• 상하좌우 비교가 아닌, 그냥 가로 , 세로 확인하는 방법으로 접근하자.
  

---

🤐주의해야 해!

• 비트마스킹 전체를 확인하는 것이 아니라, 원소 v의 값과 비교를 해야 함!
  

풀이전략

• 문제 내용
  

• 인접한 부분을 탐색하면서, 몇번 들어가는지 확인을 함.
  이런 경우는 차라리 bfs 보다는 dfs를 사용하는 것이 나음.

1. 뚫린 부분을 어떻게 처리할 수 있을까?

0,0 인 부분은 11 즉 1101
0,1 인 부분은 6 즉 0110
이다. 기준인 0,0에서 보면, 4방면을 확인하고, 0인 부분에 방문을
해야 함. 이를 비트마스킹으로 접근 할 수 있음.

• 잘못된 생각

  벽부분과 아닌 부분에 대해서 배열 형식으로 만드려는 생각을 함.
  -> 망하는 구렁텅이...

주어진 변수를 직접적으로 사용해서 처리할 수 잇는지를 생각하자!

2. 가장 넓은 방의 크기는

: dfs 돌리면서 기준으로 돌렸을 때의 몇번 방문할 수 있는지
카운팅을 하면 됨.

3. 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기?

• 하나의 그룹에 속한 방들을 동일한 이름의 번호로 매핑하자.
  : 1번 방, 2번방.

• 방들의 사이즈를 저장하는 배열을 만들자.

• 가로에 있는 벽을 제거 할 수 있고, 세로에 위치한 벽을 제거할 수 있음.
  -> 완탐으로 모든 방들을 탐색하면서 , 벽이 존재할 경우
  && 방 번호가 다를 경우에 합산을 진행함.
  1) 가로로 나뉘어서 확인.
  2) 세로로 나뉘어서 확인

코드

https://www.acmicpc.net/submit/2234/49349066