A timeout occurred when solving an algorithm problem with BFS. However, there is a problem that can be solved with DFS. Why does this difference occur?
The problem is to calculate the number of arrivals from (1,1) to (N, N) by moving horizontally, vertically, or diagonally.
It took 1331.0ms if the problem was solved by BFS (worst case), and 62.0ms when it was solved by DFS. (I have created and tested 16 * 16 arrays.)
Attach the issue URL. (But please understand that it is Korean.) URL> https://www.acmicpc.net/problem/17070
The answer I want to hear is...
Implementation code>
class Location {
int x;
int y;
int dir;
public Location(int x, int y, int dir) {
super();
this.x = x;
this.y = y;
this.dir = dir;
}
}
public class Main {
static int[][] map;
static int Answer;
static int N;
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 + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
DFS(1, 2, 0);
System.out.println(Answer);
Answer = 0;
BFS(1, 2, 0);
System.out.println(Answer);
br.close();
}
static void DFS(int x, int y, int pre) {
if (x == N && y == N) {
Answer++;
return;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
DFS(x, y + 1, 0);
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
DFS(x + 1, y, 2);
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
DFS(x + 1, y + 1, 1);
}
}
static void BFS(int startX, int startY, int dir) {
ArrayDeque<Location> arrayDeque = new ArrayDeque<>();
arrayDeque.add(new Location(startX, startY, dir));
Location location;
int x, y, pre;
while(!arrayDeque.isEmpty()) {
location = arrayDeque.remove();
x = location.x;
y = location.y;
pre = location.dir;
if(x == N-1 && y == N-1) {
Answer++; continue;
}
if (pre == 0) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else if (pre == 1) {
if (y + 1 <= N && map[x][y + 1] == 0)
arrayDeque.add(new Location(x, y + 1, 0));
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
} else {
if (x + 1 <= N && map[x + 1][y] == 0)
arrayDeque.add(new Location(x + 1, y, 2));
if (y + 1 <= N && map[x][y + 1] == 0 && x + 1 <= N && map[x + 1][y] == 0 && map[x + 1][y + 1] == 0)
arrayDeque.add(new Location(x + 1, y + 1, 1));
}
}
}
}
Both BFS and DFS have O(|V| + |E|) time complexity, and the time difference you are experiencing is most probably rooted in a mistake in the implementation of the BFS which is breaking the loop invariant.
One of the more common mistakes made while implementing BFS is adding the same element to the queue multiple times. One should only add a vertex v to the queue once, so that you can ensure it's removed a single time. Unless you do so, then the asymptotic runtime (i.e. its complexity) will not be linear anymore. You can see the relevant CLRS chapter for the proof of that, based on the loop invariant concept they introduce.
In other words, BFS is a traversal algorithm. It finds out which vertices are reachable, not the number of routes to reach every vertex v. If you try to compute the number of ways Kv to reach to each v from (1, 1) through BFS, the complexity becomes larger than linear. If the problem asks you to find Kv, then your approach should be to use memoization and dynamic programming, not BFS.
Specifically, based on the code you provided, your algorithm does not seem to keep track of whether a vertex (i e. a cell in the grid) was previously explored or not. This causes the vertices to be explored multiple times, which beats the point of using a graph traversal algorithm like BFS and DFS. Using the terminology I mentioned above, you are going against the loop invariant of BFS, which states that each vertex is popped from the queue only once. This causes the complexity of your code to go much higher than linear.
You should look into the term memoization and figure out a way to find a solutions for (N, N), using the solutions you compute only once for (N-1, N-1), (N-1, N) and (N, N-1).