sw expert academy 1953번 탈주범 검거 자바(java) 풀이
문제정리
- 탈주범은 탈출한지 1시간 뒤 지하터널의 어느 지점으로 들어갔다.
- 터널끼리 연결 되어있는 경우 이동이 가능하다.
- 탈주범은 시간당 1의 거리를 이동할 수 있다.
- 지하터널은 총 7종류의 구조물로 구성되어 있다.
- 터널이 없는 장소(구조물 X)
- 상하좌우 연결
- 상하 연결
- 좌우 연결
- 상우 연결
- 하우 연결
- 하좌 연결
- 상좌 연결
문제풀이
이 문제는 dfs가 아닌 bfs를 이용해야 풀 수 있습니다. 시간안에 해결하거나 최단 거리등과 관련된 문제는 bfs 탐색이 좋습니다.
시간에 얼마나 퍼져서 갈 수 있는지를 묻는 문제이기 때문에 bfs를 이용해야 하며 dfs를 이용하면 시간초과를 맞게 됩니다.
처음에는 간단히 생각했지만 파이프가 이어져있음을 확인하는 과정에서 생각보다 시간이 오래걸렸습니다. 이 문제는 이동하려는 파이프가 이어져있는지 확인하는 과정이 핵심이라고 생각합니다.
저는 크게 두가지 방식으로 풀었습니다.
- naive한 풀이
파이프 구조에 따른 케이스 별로 모든 경우 이어져있는지 아닌지 직접 따져 주었습니다.
Solution.java 파일에 구현되어 있습니다.
- 비트 연산
파이프의 모양을 이진수로 나타내어 비트 연산을 통해 이어져있는지 확인하였습니다.
Solution2.java 파일에 구현되어 있습니다.
naive한 풀이 (Solution.java)
우선 파이프마다 이동가능한 위치를 이차원 배열 형태로 하여 ArrayList에 모두 넣어주었습니다.
예를들어 1번 파이프의 경우 list.get(0)을 통해 1번 파이프에서 움직일 수 있는 이차원 배열을 얻을 수 있습니다
이차원 배열은 [][0] = x축 이동방향, [][1] = y축 이동방향이 됩니다.
1번 파이프의 경우 4가지로 이동가능하므로 [0][], [1][], [2][], [3][] 까지 있습니다.
2번 구조물은 상,하로 이동가능: int[][] dir = list.get(1)
상 이동: dir[0][0](x축), dir[0][1](y축)
하 이동: dir[1][0](x축), dir[1][1](y축)
각 구조물이 이어져있는지 그렇지 않은지 확인하기 위해 모든 case를 나누어주었습니다
예를들어 2번 구조물의 경우 3번 구조물이 위에있거나 아래에 있거나 모두 연결이 되지 않습니다
2번 구조물에 이동하는 곳에 4번 구조물이 있는 경우가 있을 수 있습니다. 2번 밑에 4번이 있는 경우는 이어져 있지만
2번 위에 4번이 있는 경우는 이어져있지 않습니다.
이를 다음과 같이 표현하였습니다.
// 현재 위치의 구조물이 2번인 경우
if(map[x][y] == 2){
// 다음 위치에 3번 구조물이 있는 경우 이어져있지 않음
if(map[dx][dy] == 3)
continue;
// 다음 위치에 4번 구조물이 위에 있는 경우 이어져있지 않음
// i==0 : 상, i==1 : 하
else if(map[dx][dy] == 4 && i==0)
continue;
.... 생략
}
비트 연산 이용 (Solution2.java)
1번 풀이는 알아보기 간단하지만 코드가 길게 나옵니다. 그래서 더 간단한 방법을 찾아보게 되었습니다.
구조물의 연결정보를 이진수로 표현해높으면 더욱 간단하게 확인할 수 있음을 알게되었습니다.
구조물의 표현
구조물을 다음과 같이 표현합니다.
(거꾸로 표현해도 가능)
상: 왼쪽 첫 번째 비트
하 : 왼쪽 두 번째 비트
좌 : 왼쪽 세 번째 비트
우 : 왼쪽 네 번째 비트
예를들어 1번 구조물 같은 경우는 상하좌우 이동 가능하므로 1111<sub>(2)</sub> 즉 15가 됩니다.
2번 구조물의 경우 상하로 이동 가능하므로 1100<sub>(2)</sub> = 12가 됩니다
이동가능 여부 표현
기본적으로 모든 구조물을 상하좌우 이동가능하게 합니다.
하지만 1번 구조물외에 다른 구조물들은 2가지 방향으로만 이동이 가능합니다.
그래서 이를 bit 연산을 통해 확인할 수 있습니다.
2번 구조물의 경우 1100 = 12입니다. 즉 상,하로만 이동 가능합니다. 상, 하 이동은 각각 i=0, i=1일때 입니다.
상: 1000 (i=0)
하: 0100 (i=1)
좌: 0010 (i=2)
우: 0001 (i=3)
상하좌우를 bit로 표현하기 위해서 1 << (3-i) 라는 식을 통해 표현하였습니다.
// 2번 구조물이고 상으로 이동가능한지 확인
12(1100) & 1000 != 0 => 이동 가능
// 2번 구조물이고 우로 이동가능한지 확인
12(1100) & 0001 == 0 => 이동 불가
연결여부 확인
연결된 경우에만 이동 가능하기 때문에 연결여부를 확인해줍니다. 연결 여부는 이동 방향의 반대입니다.
이동 방향과 연결부위에 따라 다음과 같은 경우에만 연결되어 있습니다.
상으로 이동인 경우 && 구조물이 하로 이동 가능해야 함 (0100)
하로 이동인 경우 && 구조물이 상으로 이동 가능해야 함 (1000)
좌로 이동 && 구조물이 우로 이동가능 해야함 (0001)
우로 이동 && 구조물이 좌로 이동가능 해야함 (0010)
예를 들어 상으로 이동하는 경우에 다음 구조물이 1번이라고 가정합시다. 그러면 다음과 같이 연결되어있는지 검증할 수 있습니다.
하(0100) & 구조물1(1111) = 0100 => 연결
상으로 이동이므로 하로 이동가능한지 확인해야 하므로 하(0100)과 비트연산을 취해야 합니다.
비트 연산을 통해 connect의 값이 그대로 나온다면 구조물에도 그 부분이 1이므로 연결되어 있음을 알 수 있습니다.
swea 탈주범 검거 자바 코드1
이 코드는 naive하게 dfs 순회를 한 코드입니다.
swea 탈주범 검거 자바 코드2
이 코드는 비트 연산을 이용해 속도를 더 향상 시킨 코드입니다.