'그래프'에 해당되는 글 3건

  1. 2018.03.31 :: 그래프이론 - 섬의 개수(백준 4963번)
  2. 2018.02.20 :: 위상정렬(백준 2252번 줄세우기)
  3. 2018.02.20 :: 그래프 DFS 와 BFS
알고리즘&자료구조/그래프&다익스트라 2018. 3. 31. 00:06

그래프이론 - 섬의 개수(백준 4963번)

1. 그래프 이론 - 섬의 개수 (백준 4963번)




2. 그래프 이론을 이용한 문제 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package _317324;
 
import java.util.Scanner;
 
public class Baekjoon4963NumberofIsland {
    static int count;
    static int[] dx= {-1,-1,0,1,1,1,0,-1};
    static int[] dy= {0,1,1,1,0,-1,-1,-1};
    static int[][] map=new int[50][50];
    static int height;
    static int weight;
    static void countIsland(int h,int w) {
        int nx=0;
        int ny=0;
        map[h][w]=2;
        for(int i=0;i<8;i++) {
            nx=w+dx[i];
            ny=h+dy[i];
            
            if(nx>=weight || nx<0 || ny>=height || ny<0) {
                continue;
            }
            if(map[ny][nx]==1) {
                countIsland(ny, nx);
            }
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        StringBuffer sb=new StringBuffer();
        while(true) {
            weight=sc.nextInt();
            height=sc.nextInt();
            if(weight==0 && height==0) break;
            
            for(int i=0;i<50;i++) {
                for(int j=0;j<50;j++) {
                    map[i][j]=0;
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    map[i][j]=sc.nextInt();
                }
            }
            for(int i=0;i<height;i++) {
                for(int j=0;j<weight;j++) {
                    if(map[i][j]==1) {
                        countIsland(i, j);
                        count++;
                    }
                }
            }
            sb.append(count+"\n");
            count=0;
        }
        System.out.println(sb);
    }
 
}
 
cs



문제의 풀이는 배열 안에 섬의 표시가 1로 표시가 되고 가로, 세로 및 대각선이 연결된 섬으로 인식이 되는 것이다. 1행부터 열을 탐색하여 1이 나오는 배열의 인덱스를 찾게 되면 그 배열의 좌표를 기준으로 countIsland 메소드를 호출하게 된다. 메소드 안에 좌표가 전달되면 전역 변수로 선언한 dx,dy 배열을 이용하여 연결된 섬을 찾게 된다. 좌표는 시작으로 부터 왼쪽, 왼쪽대각선위, 위, 오른쪽 대각선위, 오른쪽, 오른쪽 대각선 아래, 아래, 왼쪽대각선 아래를 뜻하게 된다. 그렇게 8방을 반복문으로 하나하나 따져봐서 인접한 1을 찾게 되는 것이다. 이 반복문 안에 첫번째 조건문이 뜻하는 바는 처음에 입력값으로 선언된 높이와 넓이의 직사각형을 벗어나는지를 따져보는 것이다. 만약 직사각형의 범위를 벗어나지 않으면서 팔방의 위치에 1이 존재한다면? 그 좌표를 방문했다는 표시로 모두 2로 배열의 값을 변경해준다.(그러면 더 이상 이섬은 탐색하지 않는다.)그리고 이섬은 연결된 섬으로 간주하고 그 섬의 좌표를 기준으로 countIsland 메소드를 다시 호출하게 된다. 즉, 그래프의 깊이우선 탐색을 실행하여 탐색하다가 더 이상 연결된 섬이 없을 때는 백트랙킹으로 이전의 좌표로 돌아가 이 좌표를 기준으로 다시 깊이 우선탐색을 실행하는 것이다. 그러다가 더 이상 탐색할 곳이 없게되면 함수를 종료하게 된다.(이 과정까지가 처음 발견된 1의 좌표를 기준으로 연결된 섬을 모두 탐색하고 난 후 종료하는 과정이다.) 

저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프 다익스트라 - 네트워크 복구(백준 2211번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
위상정렬(백준 2252번 줄세우기)  (0) 2018.02.20
posted by 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 20. 00:37

위상정렬(백준 2252번 줄세우기)

1. 위상정렬

위상정렬의 조건

위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다.



진입차수를 이용한 위상정렬


1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.

(방향 그래프 완성)

2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)

3. indegree가 0인 일을 모두 찾아 큐에 넣는다

4. 큐에서 정점 하나를 꺼낸다.

(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)

5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.

6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.

7. 큐가 빌 때까지 4~6을 반복한다.





2.위의 위상정렬을 이용한 백준 2252번 줄세우기 문제)




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package graph;
 
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class TopologySort {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        Queue<Integer> queue =new LinkedList<Integer>();
        int n=sc.nextInt();
        int m=sc.nextInt();
        LinkedList<Integer>[] vertexArr = new LinkedList[n];
        for(int i=0;i<n;i++) {
            vertexArr[i]=new LinkedList<Integer>();
        }
        int[] indegree=new int[n];
        for(int i=0;i<m;i++) {
            int v=sc.nextInt();
            int w=sc.nextInt();
            vertexArr[v-1].add(w-1);
            indegree[w-1]+=1;
        }
        for(int i=0;i<n;i++) {
            if(indegree[i]==0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int x=queue.poll();
            System.out.print(x+1+" ");
            Iterator<Integer> it=vertexArr[x].iterator();
            while(it.hasNext()) {
                int y=it.next();
                indegree[y]--;
                if(indegree[y]==0) {
                    queue.offer(y);
                }
            }
        }
    }
 
}
 
cs



저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
그래프 DFS 와 BFS  (0) 2018.02.20
posted by 여성게
:
알고리즘&자료구조/그래프&다익스트라 2018. 2. 20. 00:26

그래프 DFS 와 BFS


그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색)


1. 시작전

그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다.





2.DFS(깊이우선탐색)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package graph;
 
import java.util.Stack;
 
public class DFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    public DFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DFS d=new DFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        //1번 정점부터 방문시작
        d.dfs(1);
    }
 
}//결과 : 1 2 4 3 5 6 7
 
cs


설명:  1번 정점부터 시작하므로 스택에 1번정점을 넣어준다. 그리고 스택에서 peek을 하여 1번정점을 꺼내어 1번정점에 대한 인접행렬의 행을 탐색하여 첫번째로 나오는 visited가 false인 연결정점(2번정점)을 visited=true로 바꿔주고 스택에 넣어준다. 그리고 다시 스택에서 peek을 하여 이전에 넣었던 2번정점을 읽어와 2번정점에 대한 인접행렬 행을 읽어 첫번째로 나오는 visited가 false인 연결정점(4번정점)을 visited=true로 바꿔 주고 스택에 넣어준다. 이런 과정을 진행하다가 막다른 지점이 나오면(4번정점) 그에 대한 인접행렬의 행에서 visited가 false 인접한 정점이 존재하지 않으므로 스택에서 pop해주어 백트래킹을 진행한다. 그러다 1번정점에서 다시 visited가 false 인접정점이 존재하므로 위의 과정을 반복하게 된다.




3.BFS(너비우선탐색)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package graph;
 
 
import java.util.LinkedList;
import java.util.Queue;
 
import graph.DFS.Vertex;
 
public class BFS {
    class Vertex{
        public char label;
        public boolean visited;
        public Vertex(char label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=20;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Queue queue;
    public BFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        queue=new LinkedList();
    }
    public void addVertex(char label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.println(vertexList[v].label);
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BFS d=new BFS();
        d.addVertex('1');
        d.addVertex('2');
        d.addVertex('3');
        d.addVertex('4');
        d.addVertex('5');
        d.addVertex('6');
        d.addVertex('7');
        
        d.addEdge(0,1); //1->2
        d.addEdge(1,3); //2->4
        d.addEdge(0,2); //1->3
        d.addEdge(2,4); //3->5
        d.addEdge(2,5); //3->6
        d.addEdge(2,6); //3->7
        d.bfs(1);
    }
 
}//결과: 1 2 3 4 5 6 7
 
cs


설명: 시작정점 1번을 방문후 큐에 삽입해준다. 그리고 큐에서 poll을 해서 1번정점을 빼주고 1번노드 다음레벨에 해당하는(인접하고있는) 정점들을 모두 방문 후 큐에 삽입해준다.(2번정점 3번정점) 그리고 큐에서 poll을 해서 2번정점을 빼주고 2번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(4번정점) 그다음 큐에서 poll을 해 3번 정점을 빼주고 3번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(5,6,7번정점).. 이과정을 반복해준다.




4. 백준 1260번 DFS와 BFS  



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package graph;
 
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
public class DFSBFS {
    class Vertex{
        public String label;
        public boolean visited;
        public Vertex(String label) {
            this.label=label;
            this.visited=false;
        }
    }
    private final int maxVertices=1000;
    private Vertex[] vertexList;
    private int Matrix[][];
    private int vertexCount;
    private Stack stack;
    private Queue queue;
    public DFSBFS() {
        vertexList=new Vertex[maxVertices];
        Matrix=new int[maxVertices][maxVertices];
        vertexCount=0;
        for(int y=0;y<maxVertices;y++) {
            for(int x=0;x<maxVertices;x++) {
                Matrix[x][y]=0;
            }
        }
        stack=new Stack();
        queue=new LinkedList();
    }
    public void addVertex(String label) {
        vertexList[vertexCount++]=new Vertex(label);
    }
    public void addEdge(int start, int end) {
        Matrix[start][end]=1;
        Matrix[end][start]=1;
    }
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label+" ");
    }
    public void dfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        stack.push(n-1);
        while(!stack.isEmpty()) {
            int v=getAdjUnvisitedVertex((int) stack.peek());
            if(v==-1) stack.pop();
            else {
                vertexList[v].visited=true;
                displayVertex(v);
                stack.push(v);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public void bfs(int n) {
        vertexList[n-1].visited=true;
        displayVertex(n-1);
        queue.offer(n-1);
        int v2;
        while(!queue.isEmpty()) {
            int v1=(int) queue.poll();
            while((v2=getAdjUnvisitedVertex(v1))!=-1) {
                vertexList[v2].visited=true;
                displayVertex(v2);
                queue.offer(v2);
            }
        }
        System.out.println();
        for(int j=0;j<vertexCount;j++) {
            vertexList[j].visited=false;
        }
    }
    public int getAdjUnvisitedVertex(int v) {
        for(int j=0;j<vertexCount;j++) {
            if(Matrix[v][j]==1 && vertexList[j].visited==false) return j;
        }
        return -1;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        DFSBFS ma=new DFSBFS();
        int n=sc.nextInt();
        int m=sc.nextInt();
        int v=sc.nextInt();
        
        for(int i=0;i<n;i++) {
            ma.addVertex(i+1+"");
        }
        while(m!=0) {
            ma.addEdge(sc.nextInt()-1,sc.nextInt()-1);
            m--;
        }
        ma.dfs(v);
        ma.bfs(v);
    }
 
}
 
cs


저작자표시

'알고리즘&자료구조 > 그래프&다익스트라' 카테고리의 다른 글

그래프이론 - 섬의 개수(백준 4963번)  (0) 2018.03.31
최소신장트리-프림알고리즘(백준 1197번)  (0) 2018.02.22
최소비용구하기-다익스트라알고리즘(백준 1916번)  (0) 2018.02.22
최단거리-다익스트라알고리즘(백준 1753번 문제)  (0) 2018.02.22
위상정렬(백준 2252번 줄세우기)  (0) 2018.02.20
posted by 여성게
:

티스토리툴바