14502 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

1.접근

바이러스가 퍼진다는 것을 보면 DFS를 쓰면 되겠다는 생각이 든다. 조건으로 0인 부분에 벽을 3개 세워야 한다고 하니

itertools의 combination을 이용해서 0인 부분으로 3개의 모든 조합을 만들고 모든 상황을 DFS 해보고 제일 바이러스가 적게 퍼지는 상황을 구하면 되겠다.

2.풀이

우선 배열을 입력받고 행과열 양끝에 벽이 있는 것처럼 1로 입력을 감싸준다.

다음으로 배열을 돌면서 0인 부분과 2인 부분을 뽑아낸다.0인 부분은 벽이 될 수 있게 배열을 만들어서 조합을 만들 것이고 2인 부분은 배열을 만들어서 모두 DFS할 것이다.

내가 조심하지 않았던 부분은 원래의 입력받은 배열 adj를 변형시키지 않고 복사시키는 부분이였다.

temp배열은 2차원 배열로 temp도 mutable하고 temp속의 원소들도 리스트로 mutable했기 때문에 

내부의 각 리스트를 따로 할당해야 한다(shallow copy).

adj를 만들 때 1로 감싸준 것은 list out of index를 방지하면서도 속도를 빠르게 하기 위함이다.

 

3.코드

4.배운점

• 문제를 풀면서 배운게 많다. 우선 mutable한것과 immutable한것을 외웠다. 2차원 배열은 리스트안에 리스트가 있는 구조라 b=a[:]로 해결되지 않고 한 배열씩 모두 해주어야했다.

• shallow copy를 했을 때 새로운 값을 할당하면 주소가 바뀌면서 문제가 없지만 변경하는 경우(append 같은)에는 같이 변경된다. 큰 틀은 주소가 달라지지만 내부의 객체는 같은 주소를 갖는 것을 기억하자.

• 이번에 원래 풀던방식인 dx,dy를 [0,0,-1,1],[1,-1,0,0]으로 만들고 for문을 돌려서 4 방향을 찾아가는 방식으로 구현했었다.하지만 문제를 풀었을 때 빠르게 풀린코드와 2배이상의 시간차이가 나는 것을 보고 공부를 했는데 배열의 양끝을 크게 만들고 for문 대신 직접 -1,+1을 구사하는 것이 시간이 중요한 DFS나 BFS문제에서 훨씬 빠르다는 것을 배웠다.

• count도 자주쓰자 까먹고있었다.

wikidocs.net/16038 deepcopy,shallowcopy 정리된곳