Escape

Code

import java.util.LinkedList;

public class Escape

{

    int[] dx = {1,0,-1,0};

    int[] dy = {0,1,0,-1};

    int[][] map, dist;

    boolean[][] used;

    class node {

        int x,y;

        node(int x, int y) {

            this.x = x;

            this.y = y;

        }

    }

    public int lowest(String[] harmful, String[] deadly) {

        if(harmful.length == 0 && deadly.length == 0) return 0;

        map = new int[501][501];

        dist = new int[501][501];

        used = new boolean[501][501];

        setMap(harmful, 1);

        setMap(deadly, 2);

        return bfs();

    }

    void setMap(String[] str, int v) {

        for(int i=0; i < str.length; i++) {

            String[] s = str[i].split(" ");

            int x1 = Integer.parseInt(s[0]);

            int y1 = Integer.parseInt(s[1]);

            int x2 = Integer.parseInt(s[2]);

            int y2 = Integer.parseInt(s[3]);

            if(x1 > x2) {

                int temp = x1;

                x1 = x2;

                x2 = temp;

            }

            if(y1 > y2) {

                int temp = y1;

                y1 = y2;

                y2 = temp;

            }

            for(int a=x1; a <= x2; a++)

                for(int b=y1; b <= y2; b++)

                    map[a][b] = v;

        }

    }

    int bfs() {

        LinkedList<node> q = new LinkedList<node>();

        q.add(new node(0,0));

        map[0][0]=2;

        int min=-1;

        while(!q.isEmpty()) {

            node n = q.poll();

            if(n.x==500 && n.y==500) min = dist[500][500];

            for(int i=0; i < 4; i++) {

                int x = n.x + dx[i];

                int y = n.y + dy[i];

                if(x<0 || y<0 || x>500 || y>500 || map[x][y]==2) continue;

                if(used[x][y] == true) {

                    if(dist[n.x][n.y] + map[x][y] < dist[x][y]) {

                        dist[x][y] = dist[n.x][n.y] + map[x][y];

                        q.add(new node(x,y));

                    }

                }

                else {

                    used[x][y] = true;

                    dist[x][y] = dist[n.x][n.y] + map[x][y];

                    q.add(new node(x,y));

                }

            }

        }

        return min;

    }

}

Explanation

처음에 재귀로 풀었는데 스택 오버플로우가 일어나서 실패했다. 답을 알아보니 Breadth first search (bfs) 를 이용해야 됐었다. 이 문제는 그래프나 트리를 사용하지 않아도 답을 구할 수 있어서 그래프나 트리를 사용하지 않았다.

q에 추가한 정점 x,y는 used[x][y] = true; 로 지정한다. 후에 다른 지점에서 이 정점 x,y로 들어올 때 기존 값보다 작다면 새 값으로 변경 후 다시 q에 넣는다.

BFS : 트리나 그래프를 통해 자료를 탐색해 나가는 알고리즘

Breadth-First-Search(Graph, root):

for each node n in Graph:

    n.distance = INFINITY

    n.parent = NIL

create empty queue Q

root.distance = 0

Q.enqueue(root)

while Q is not empty:

    current = Q.dequeue()

    for each node n that is adjacent to current:

        if n.distance == INFINITY:

            n.distance = current.distance + 1

            n.parent = current

            Q.enqueue(n)Breadth-First-Search(Graph, root):

References

https://github.com/jskonhovd/TopCoder/blob/master/Java/Escape.java

https://en.wikipedia.org/wiki/Breadth-first_search