1. 문제
백준 17070번 파이프 옮기기 1 - https://www.acmicpc.net/problem/17070
✅ 알고리즘 분류 - 그래프 탐색, 다이나믹 프로그래밍
🥇 난이도 - Gold 5
2. 풀이
해당 문제는 DP로도 풀 수 있으나 저는 DFS를 이용한 브루트 포스로 풀었습니다.
- NxN의 크기를 가진 2차원 배열(pipeCnt)을 만들고 DFS를 이용하여 파이프가 이동할 수 있는 모든 경우를 다 수행합니다.
- 이동에 성공할때마다 2차원 배열(pipeCnt)에서 이동지점에 해당하는 위치에 1을 더해줍니다. 이렇게 하면 2차원 배열(pipeCnt)은 각 지점마다 파이프가 올 수 있는 방법의 수를 저장하는 배열이 됩니다.
- 최종적으로 2차원 배열에서 (N,N)위치의 값을 출력하면 정답입니다.
참고로 파이프가 두 칸을 차지하지만 파이프가 NxN의 격자판 밖으로 튀어나올 수 없다는 조건이 있기 때문에 파이프가 차지하는 오른쪽 칸만으로 DFS를 수행하면 됩니다.
(만약 해당 조건이 없다고 해도 동일하게 수행한 후 (N,N)에 놓여져 있으면서 NxN의 격자판 밖으로 튀어나온 경우의 수인 3을 빼면 됩니다)
3. 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static int[][] map;
public static int[][] pipeCnt;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n][n];
pipeCnt = new int[n][n];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<n; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
dfs(0,1,0);
System.out.println(pipeCnt[n-1][n-1]);
}
/**
* @param r : row
* @param c : column
* @param rotate : 0 = 가로, 1 = 대각선 2 = 세로
*/
public static void dfs(int r, int c, int rotate) {
if (r>=n || c>=n || map[r][c]==1) return;
if (rotate==0) {
dfs(r,c+1,0);
dfs(r+1,c+1,1);
} else if (rotate==1) {
if (map[r-1][c]==1 || map[r][c-1]==1) return;
dfs(r,c+1,0);
dfs(r+1,c+1,1);
dfs(r+1,c,2);
} else {
dfs(r+1,c+1,1);
dfs(r+1,c,2);
}
pipeCnt[r][c]++;
}
}4. 결과
5. 풀이 과정
처음 문제를 보았을때는 DFS나 BFS로 완전탐색하는 문제라고 생각했습니다.
다만 동일한 정점에 대한 재방문을 허용해야하기 때문에 방문여부를 확인하지 않는 방식으로 구현하기로 생각했습니다.
DFS나 BFS 둘다 방문하는 정점의 최종 개수는 동일하니까 평소 더 선호하던 방식인 BFS로 구현하였더니 시간초과가 났습니다. 해당 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int n;
public static int[][] map;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = Integer.parseInt(br.readLine());
map = new int[n][n];
for (int i=0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for (int j=0; j<n; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(bfs());
}
public static int bfs(){
int cnt = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0,1,0}); //[r,c,rotate] rotate: 0=가로, 1=대각선, 2=세로
while (!q.isEmpty()) {
int[] p = q.poll();
if (p[0]==n-1 && p[1]==n-1) {
cnt++;
continue;
}
if (p[2] == 0) {
if (p[1]+1<n && map[p[0]][p[1]+1]==0)
q.offer(new int[]{p[0], p[1] + 1, 0});
if (p[0]+1<n && p[1]+1<n && map[p[0]+1][p[1]+1]==0 && map[p[0]+1][p[1]]==0 && map[p[0]][p[1]+1]==0)
q.offer(new int[]{p[0]+1,p[1]+1,1});
} else if (p[2] == 1) {
if (p[1]+1<n && map[p[0]][p[1]+1]==0)
q.offer(new int[]{p[0], p[1] + 1, 0});
if (p[0]+1<n && p[1]+1<n && map[p[0]+1][p[1]+1]==0 && map[p[0]+1][p[1]]==0 && map[p[0]][p[1]+1]==0)
q.offer(new int[]{p[0]+1,p[1]+1,1});
if (p[0]+1<n && map[p[0]+1][p[1]]==0)
q.offer(new int[]{p[0]+1,p[1],2});
} else {
if (p[0]+1<n && p[1]+1<n && map[p[0]+1][p[1]+1]==0 && map[p[0]+1][p[1]]==0 && map[p[0]][p[1]+1]==0)
q.offer(new int[]{p[0]+1,p[1]+1,1});
if (p[0]+1<n && map[p[0]+1][p[1]]==0)
q.offer(new int[]{p[0]+1,p[1],2});
}
}
return cnt;
}
}그 다음으로 생각난 방법은 DP였지만 N이 최대 16밖에 되지 않고 시간 제한도 1초였기 때문에 아무리 봐도 완전탐색으로도 풀 수 있어 보였습니다.
그래서 시간초과가 나는 이유를 알기위해 검색을 했더니 저처럼 BFS를 사용하고 시간초과가 난 사람들이 많아 보였습니다.
그래서 이번에는 동일한 로직을 DFS로 구현하였더니 통과되었습니다.
분명 제가 알기로는 DFS나 BFS나 방문하는 정점의 개수는 동일한데 dfs만 통과되는 이유가 궁금해서 각 방식의 걸리는 시간과 방문하는 정점의 갯수를 직접 측정해 보았고 결과는 다음과 같이 나왔습니다.
테스트 케이스는 N이 16이고 배열의 값은 전부 0입니다.
생각했던대로 방문한 정점의 개수는 동일하였으나 걸린시간에는 큰 차이가 있었습니다.
그래서 이와 같은 결과가 나온 이유를 생각해 보았는데 방문하는 정점마다 수행해야하는 if문이 dfs보다 bfs가 더 많았기 때문이라고 생각됩니다. (만약 제 생각이 틀렸거나 관련하여 아시는 분이 있다면 알려주시면 감사하겠습니다.)
