해시함수를 통한 방문처리

 

2차원 grid 가 주어지는 여러 알고리즘 문제 거의 대부분은 grid 순회 및 탐색이 문제의 해결과정에 포함되어 있고, 이 과정은 dfs, bfs 로 이루어진다. dfs, bfs 에서 중요한건 중복방문을 제거하기 위한 방문처리인데 쉽고 간단한 방법은 동일한 사이즈의 2차원 grid 를 할당받아  해당 자료구조에 방문여부를 표시한다. 이후에 좌표값의 유효여부를 포함해 해당 좌표로의 탐색이 가능한지 판별한다

 

 

public static boolean isPosValid(int[][] grid, boolean[][] isVisited, int row, int col) {
    int rowSize = grid.length;
    int colSize = grid[0].length;

    return row >= 0 && col >= 0 && row < rowSize && col < colSize && isVisited[row][col];
}

 

 

근데 아래 문제에서는 정말 까다로운 조건을 내걸었다

 

 

[BOJ] 23289 - 온풍기 안녕! ( 삼성 SW 역량테스트 기출 ) (tistory.com)

[BOJ] 23289 - 온풍기 안녕! ( 삼성 SW 역량테스트 기출 )

 

 

벽이 존재하지만, 이는 gird 상의 데이터로 표현되는것이 아니라 좌표간의 상태로 표현되었다

 

 

빨간 선이 벽이다

 

이제 gird 의 탐색에 있어서, 단일 좌표의 탐색가능 여부가 아닌, 좌표간의 이동여부를 확인하는 형식으로 문제가 발전되었다

좌표간의 이동여부를 저장해야 할 별도의 자료구조가 필요했고, 나는 이를 해시맵을 통해 해결하기로 했다

 

---

문자열 해시

 

초기 아이디어는 문자열을 활용한 벽 상태의 저장이었다

시작좌표, 끝좌표가 주어질 때 이들을 해시충돌이 일어나지 않을 문자열로 저장해 Set 으로 관리했다

 

public static void updateWallInfo(Set<String> wallInfoSet, int srcRow, int srcCol, int destRow, int destCol) {
	wallInfoSet.add(getWallInfoHashValue(srcRow, srcCol, destRow, destCol));
}

// 이 경우 해시값은 해시충돌이 일어나지 않게 하는게 매우 중요하다
// String.format("%d%d%d%d", srcRow, srcCol, destRow, destCol) 와 같은 단순 숫자의 concatnate 로 해시값을 설정할 경우
// {[0,0] -> [1, 10]} 과 {[0,0] -> [11, 0]} 모두 동일한 00110 이라는 동일한 해시값으로 인해 해시충돌이 발생
// delimiter 를 적절히 넣어주는게 중요
public static String getWallInfoHashValue(int srcRow, int srcCol, int destRow, int destCol){
	return String.format("[%d,%d][%d,%d]", srcRow, srcCol, destRow, destCol);
}

 

문제는 매번 좌표간의 탐색 시 이동가능여부를 확인하면서 수많은 String 개체를 heap 에 생성함으로서 소모되는 시간과 ( OS 로부터 메모리 할당 == syscall -> context switch )

한번쓰고 버리는 String 개체들로 인한 잦은 gc 호출

더불어 String 의 해시값 연산까지 ( Java 버전에 따라 다르겠지만 default String.hashCode 는 정확성과 연산속도 그 중간에서 합의를 본 로직으로 구현되어 있어서 느리지는 않지만 빠르지도 않다 )

위 3단콤보로 인해 프로그램을 실행하면...

 

초당 채첨현황이 1%가 안올라간다

 

위와 같은 극악의 런타임이 탄생하며 시간초과로 실패한다, 백준 플랫폼을 사용하면서 이렇게 느린 채점속도는 처음 봤다...

 

Java 에서는 특정 로직에서 발생하는 String 개체의 잦은 생성으로 인한 문제를 해결하기 위해 언어단으로 StringBuilder 와 StringBuffer 를 지원한다

하지만 이는 어디까지나 Immutable한 String 개체의 연산의 중간과정에서 자주 생성되는 문제를 버퍼링을 통해 해결해주는거지

위의 경우와 같이 최종 연산값인 String 의 잦은 할당을 해결해주지는 못한다

 

따라서 문자열을 활용한 해시값은 효율적인 해결책이 되지 못한다

 

---

정수 해시

 

Java 의 String 개체는 Set.add 나 Set.contains 메소드 호출의 인자로 들어갈 경우, 내부적으로 int 를 리턴하는 String.hashCode 를 호출한다.

따라서 해당 과정을 직접 구현한다면, 잦은 String 개체 할당으로 인한 이슈는 해결할 수 있다

 

위에서도 언급했듯이 해시함수를 직접 만들때는 해시충돌에 특히나 조심해야 한다

대부분의 상황에서는 값의 범위가 주어져 있으므로 n 진법을 응용한다면 충돌없는 해시함수를의 구현이 가능하다

 

당연한 얘기지만, 10진법에서는 각 자리의 숫자는 유니크하다 ( 0 ~ 9 )

만약 좌표값의 범위가 0 ~ 19 로 한정되어 있다면 20진법으로 충돌없는 해시값 생성이 가능하다

 

public static void updateWallInfo(Set<Integer> wallInfoSet, int srcRow, int srcCol, int destRow, int destCol) {
    wallInfoSet.add(getWallInfoHashValue(srcRow, srcCol, destRow, destCol));
}

// [destCol][destRow][srcCol][srcRow] 의 형태의 20진법
public static Integer getWallInfoHashValue(int srcRow, int srcCol, int destRow, int destCol){
    return srcRow + ( srcCol * 20 ) + ( destRow * 20 * 20 ) + ( destCol * 20 * 20 * 20 );
}

 

 

주어진 값의 범위에 따라 해시값이 int 범위를 넘어서는지를 꼭 확인하고, 이에따라 적절한 type 을 선택해야한다

해시값의 최대값은 20 ^ 4 - 1 인 15999 로 int 범위를 넘지 않는다

 

이를 응용한다면, 2 차원 grid 에서의 좌표값 뿐만 아니라, Directed Graph 에서의 노드 방문처리도 가능하다 v