Iceberg

문제 복기

알고리즘 생각 1. 빙하 깍는다. 2. 빙하 수 센다.

레퍼런스를 찾아봤는데 일단 문제 접근방법은 맞다고 할 수 있겠다. 그렇다면 틀린 이유는 로직, 알고리즘을 코드로 구현하는 것에 있어서 틀린 부분이 있었던 것 같다.

단순해보이면서 복잡한 것 같은 로직을 구현할 때 하나씩 차근히 구현해보자.

1. 빙하 크기를 1씩 줄인다.

2. (1이 제대로 실행된다면 )빙하 갯수 센다.

3. 1+2 병합. 1을 반복해서 실행한다. 2의 갯수가 2개가 될 때까지.

틀린 이유(틀린 부분) 1. 빙하 감소시키는 Melt() 함수에서 상하좌우 탐색 : 0인 인접노드를 찾아서 갯수를 셀 때, visited로 방문체크하여 방문한 노드(visited가 true)는 다시 방문하지 않도록 했다. 이렇게 되면 visited가 true로 되버린 빙하 노드는 방문되었다고 체크되어서 빙하깍는 연산이 실행되지 않았다. 그래서 0인 인접녿드를 찾아서 0의 갯수를 세는 것만 구현을 해주는 것으로 고쳤다! 2. Melt() 함수에서 0갯수만큼 빙하 감소시키기 : a[x][y]-zeroCnt가 0이상일 때만 처리해주도록해버려서 빙하높이보다 주변 0갯수가 많은 경우 빙하가 감소되지 않았다! 수정 전 :

if(a[cur.x][cur.y]-zero_cnt <0) continue;
else {
		a[cur.x][cur.y]-=zero_cnt;
}

수정 후 :

if(a[cur.x][cur.y]-zero_cnt <0) {
	a[cur.x][cur.y] = 0;
}
else {
		a[cur.x][cur.y]-=zero_cnt;
}

3. 빙하 갯수 세는 IBCnt() 함수 : 일반적인 BFS/DFS 함수를 구현하면 되는데 중복 방문을 체크하는 배열 객체 visited를 전역변수로 설정해버려서 그래프 순회를 한번하고나면 전체 노드가 방문처리되어 IBCnt함수를 다시 호출할 때 조건을 전혀 만족하지 않아 빙하갯수는 0개가 되버린다. 그러므로 IBCnt()함수와 이 함수내부에서 BFS 또는 DFS 함수에서 중복 방문 체크 visited를 생성하여, DFS/BFS에 전달해주어서 방문 체크를 하도록 한다!

코드 리팩토링

1. Scanner와 System.out.print를 사용한 입출력보다 BufferedReader,BufferedWriter, StringTokenizer를 사용한 입출력이 약 400ms 빠른 것을 확인할 수 있었다. 코딩 테스트는 속도가 빠른 것이 좋으므로 후자를 안 쓸 이유가 없다!

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		r = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		a = new int[r][c];
		for(int i=0;i<r;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<c;j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
...
bw.write(ans+"\n");
bw.flush();
bw.close();
br.close();

마지막에는 꼭 BufferedWriter.flush()와 BufferedWriter.close(), BufferedReader.close()를 해주어야한다!!!!

2. while루프 개선 : 90ms, 2300kb 시공간을 절약할 수 있었다!!! while문 조건을 true로 하여 무한루프로 만들고, 무조건 실행하는 함수를 앞에 두고, 종료 조건을 뒤어 두었다. 개선 전 :

while(true) {
			Melt();year++;
			if(IB5Cnt()>=2) break;
			else if(IB5Cnt()==0){
				year = 0;
				break;
			}
		}

개선 후 :

while((cnt = IB5Cnt()) < 2) {
			if(cnt == 0) {
				year = 0;
				break;
			}
			Melt();
			year++;
		}