chainpark   2년 전

코드는 다음과 같이 짰습니다.


1. 2차원 배열 int a[x][y]에 입력을 받음 동시에 큐에 1이 들어가는 index i,j 를 push

2. bool visit[x][y]에 해당 index x y의 방문 여부 표기

3. BFS로 탐색시작.
   3-1) 큐의 front의 좌표를 가져오고, visit에서 방문 표시

   3-2) 상하좌우의 조건을 토대로 탐색 결정(방문한 적 없고 해당 위치에 배추가 심어져있을 경우(1일경우) 방문하고, 해당 위치를 0으로 초기화)

   3-3) 상하좌우 탐색이 끝난 큐의 front pop

   3-4) 3-1부터 반복

4. 전체 배열 내의 1의 갯수를 집계, ans로 출력


BFS를 잘 못 설정한 것일까요? 테스트 케이스의 경우는 맞아떨어졌습니다.


저렇게한게 각 덩어리의 시작점은 1로 남지만 각 덩어리의 나머지는 다 0으로 초기화되서 카운트 하기 쉽고


visit의 여부를 조건으로 탐색을 하고 visit의 값에도 변화를 주기 때문에 원형 데이터의 요소가 유지될 것이라는 생각에 저렇게 코드를 짰습니다.

djm03178   2년 전

int nx = x + dx[i];

int ny = y + dy[i];

if (a[nx][ny] == 1&&visit[nx][ny]==false)

nx와 ny가 배열의 범위를 벗어나지 않는다는 보장이 있나요?

chainpark   2년 전

고맙습니다. 범위 설정을 해주니 런타임 에러는 해결됬는데 결국 답안은 틀렸네요. 반례 잘 찾아서 해결해보겠습니다. 감사합니다

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