BitmapToGraph

Code

import java.util.TreeSet;

public class BitmapToGraph

{

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

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

    int n,m;

    String[] bmap;

    char check(int nx, int ny) {

        return (nx<0 || nx>=m || ny<0 || ny>=n) ? '.' : bmap[ny].charAt(nx);

    }

    

    public String[] parse(String[] bitmap) {

        bmap = bitmap;

        n = bitmap.length;

        m = bitmap[0].length();

        int node = 0;

        int[][] num = new int[n][m];

        for (int i = 0; i < n; i++)

            for (int j = 0; j < m; j++)

                if (bitmap[i].charAt(j) == 'N')

                    num[i][j] = node++;

        boolean[][] e = new boolean[n][m];

        String[] res = new String[node];

        for (int i = 0; i < node; i++) res[i] = "";

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

            for (int j = 0; j < m; j++) {

                if (bitmap[i].charAt(j) == 'N') {

                    TreeSet<Integer> set = new TreeSet<Integer>();

                    for (int d = 0; d < 8; d++) {

                        int nx = j + dx[d];

                        int ny = i + dy[d];

                        if (check(nx,ny)=='E' && e[ny][nx]) continue;

                        int d1 = d;

                        int cnt = 0;

                        while (check(nx,ny) == 'E') {

                            if (check(nx+dx[d1],ny+dy[d1]) == '.') {

                                if (check(nx+dx[(d1+7)%8],ny+dy[(d1+7)%8]) != '.')

                                    d1 = (d1+7)%8;

                                else if (check(nx+dx[(d1+1)%8],ny+dy[(d1+1)%8]) != '.')

                                    d1 = (d1+1)%8;

                            }

                            nx += dx[d1];

                            ny += dy[d1];

                            cnt++;

                        }

                        if (cnt != 0) {

                            if (num[i][j] == num[ny][nx]) e[ny-dy[d1]][nx-dx[d1]] = true;

                            set.add(num[ny][nx]*100000+cnt*10+d);

                        }

                    }

                    boolean comma = false;

                    for (int s : set) {

                        if(comma) res[num[i][j]] += ",";

                        res[num[i][j]] += s/100000 + ":" + (s%100000)/10;

                        comma = true;

                    }

                }

            }

        }

        return res;

    }

}

Explanation

boolean[][] e는 단일 고리(self loop)의 마지막 변을 나타내기 위한 배열이다. 이를 통해 단일 고리는 정확히 한 번만 더해진다.

(d1+7)%8과 (d1+1)%8을 통해 45도 각도로 나아갈 수 있다. 자리수 계산을 위해 목적지 노드 숫자에 100000을 곱하고 길이에 10을 곱한다. d를 더해주는 것은 같은 길이를 가진 방향이 다른 변들을 허용하기 위함이다.

References

https://community.topcoder.com/stat?c=problem_solution&cr=156216&rd=4701&pm=1882

https://community.topcoder.com/stat?c=problem_solution&cr=309453&rd=4701&pm=1882