(JAVA) 백준 14502번 : 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

시뮬레이션 + DFS 문제이다.

 

 

 

 

짚고 넘어갈 부분은

 

 

 

  1.  무조건 바이러스는 시간 상관없이 퍼진다.

    -> 따라서, 다 퍼지고 퍼질 곳이 없을 때 바이러스 확산 함수를 종료한다.

 

 

  2.  벽은 정확히 3개를 추가한다. 더 많이 또는 더 적게 추가할 수 없다.

 

 

  3.  벽은 '0' 위치(= 빈 땅) 에만 추가할 수 있다. '1' 또는 '2' 에는 추가할 수 없다.

 

 

  4.  바이러스가 더이상 퍼지지 않을 때 안전한 구역의 개수 최댓값을 구하는 문제이다.  

    -> '1' 과 '2' 가 아닌 '0' 의 개수가 최대인 값이다.

 

 

매커니즘

---

1.  백트래킹(Back Tracking) 으로 '0'인 위치들 중 3곳을 '1'(=벽) 로 변경한다.

 

2.  3개가 세워지면, DFS를 사용해 바이러스를 확산한다. (해당 함수 실행)

 

3.  확산이 끝나면, '0'의 개수를 count해서 Math.max를 통해 최댓값을 저장한다.

 

 

 

 

 

*** 문제를 풀다가 한 가지 배웠습니다.

*** 백트래킹 함수 진행 시 파라미터로 배열을 사용해서 진행해도 됩니다.

그 이유는, 배열 참조 값은 같아도 재귀 호출 이후 다시 돌아와서 값을 이전으로 변경시키기 때문입니다.

 

 

*** 또, 2차원 배열 백트래킹 시 2중 for문(x 좌표, y 좌표) 을 사용하기 보다는

배열의 길이(x, y)를 곱한 값을 max로 for문 하나만 돌려서 진행하는 것이 더욱 좋고, 이해하기도 쉽다.

 

ex)

for(int i = 0; i < y; i++) {

 for(int j = 0; j < x; j++) {

  map[i][j];

 }

}

 

보다는

 

for(int index = 0; index < x * y; index++) {

  int y = index / x;

  int x = index % y;

}

 

로 2차원 배열 for문을 작성하면 덜 헷갈리고 좋다.

 

 

 

 

 

 

감사합니다!

 

 

소스코드

---