백준 14502 연구소

domybest·2021년 4월 15일
0

백준

목록 보기
27/36
post-thumbnail

풀이 코드
문제

알고리즘

문제를 보면 n과 m의 값이 8 이하로 매우 작은 것을 알 수 있다. 따라서 모든 경우의 수를 따지는 알고리즘을 적용하는 문제임을 짐작해 볼 수있다. 3개의 벽을 설치한다고 하였는데 이 3개의 벽 위치에 대한 모든 경우의 수를 따져 문제를 푼다. n * m의 보드 위에서 3개의 위치를 뽑는 '조합'이다.
깃허브에 올린 코드에서는 다음과 같이 조합을 구했다.

			for(int i = 0; i < n; i++) {
				for(int j = 0; j < m; j++) {
					if(map[i][j] == 0) {
						map[i][j] = 1;
						count++;
						dfs(count);
						map[i][j] = 0;
						count--;
					}
				}
			}

모든 행과 열을 탐색하는 대신 벽이 설치되어 있지 않고 바이러스가 없는 곳에만 벽을 세우고 3개를 세울 때까지 재귀적으로 탐색해 가는 방식이다. 실제 이 코드를 돌리면 500ms 정도의 시간이 나온다. 그래서 시간을 더 줄일 수 없을까에 대해 검색하던 도중 2차원 배열에서 조합을 구하는 방법에 대해 보았다.

public static void dfs(int start, int count) {
		if(count == 3) { // 3개의 기둥이 모두 설치 됐으면 안전 상태인 곳을 구해 개수 세기
			copy_array();
			//바이러스 퍼트려 나가
			//바이러스에서 퍼져 나가는 거니까 바이러스의 위치를 시작점으로 줘야겠구나. 
			//바이러스의 위치를 알아야 겠구나 -> list
			for(Node node : virus_list) {
				virus_spread(node.i, node.j);
			}
			//남은 0의 개수 세서 max 변수 변경
			max = Math.max(max, cal_safe());
		}
		else { // 아직 3개의 기둥이 모두 설치되지 않았으면 남은 조합으로 하나 더 설치하기
            for(int i = start; i<n*m;i++){
            int x = i / m;
            int y = i % m;
            if(map[x][y]==0){
                map[x][y]=1;
                dfs(i + 1, count + 1);
                map[x][y] = 0;
            }
        }	
		}
	}

다음과 같이 start부터 전체 원소 개수만큼 for문을 돌고 x는 나누기 열의 개수, y는 나머지 열의 개수 연산으로 구하면 모든 조합을 구할 수 있다는 것이다. 실제 코드를 돌려보면 300ms로 200ms나 줄어든 것을 확인할 수 있었다. 얼핏보면 둘 다 반복문을 n * m번 도는 것 아니냐고 생각할 수 있지만 후자는 진행하면 할수록 i의 초깃값이 바뀌어 반복문의 반복 횟수가 줄어들게 된다. 거기서 차이가 발생한 것 같다. 해당 스킬은 기억해 두는 것이 좋겠다.

조합을 구했으니 3개의 벽을 세운 후에 바이러스를 퍼트리는 것을 구현해야 겠다. 지금까지 공부해온 전형적인 dfs 문제이다. 다만 기존에는 모든 원소를 탐색하여 퍼트렸다면 이 문제에서는 시작점, 즉 바이러스의 위치에서 퍼트려야 한다. 그래서 바이러스의 위치 정보를 저장하는 list를 만들어야 한다. 그리고 바이러스의 위치에서 바이러스를 퍼트리는 dfs 함수를 작성한다.

이제 최종 배열에서 0의 개수를 찾아 max 값을 갱신해 주면 문제는 해결된다. 다음 조합에서 또 같은 과정을 반복하기 위해서는 map의 원소값들을 원래대로 돌려놔야 하기 때문에 copy 배열이 하나 더 필요함을 인지해야 겠다.

자바 깊은복사와 얕은복사

코딩팩토리 블로그 참고 게시물
얕은 복사란 복사물의 변경이 원본에도 영향을 끼치는 것을 말한다. 깊은 복사는 서로 영향을 끼치지 않는 것을 말한다. 깊은 복사를 위해서 일반적으로 for문을 통해 일일이 대입해야 한다. 하지만 1차원 배열에서 만큼은 여러 메서드를 제공한다. 대표적으로 arr.clone() 등의 clone() 메서드가 존재한다.
그러나 2차원 배열에서 만큼은 깊은 복사가 불가능하다. 즉, for문을 통해서만 copy를 진행해야 함을 기억하자.

profile
기억할 때 까지 반복!

0개의 댓글