Posted Updated Algorithm

경로찾기

https://www.acmicpc.net/problem/11403

다시 푼 문제이다. DFS를 이해하고 있으면 쉬운 문제이다.

풀이

  1. 각각의 정점에서 차례대로 DFS를 실행한다.
  2. 연결된 정점이 있고 아직 방문하지 않았으면, 방문 체크 후에 연결된 정점에서 다시 DFS를 실행한다.
  3. 경로를 출력한다.

예시

위의 경우를 생각해보자.

  • 0을 시작으로 DFS를 실행한다.
    • 0과 연결된 정점은 1이다. 1은 아직 방문하지 않았으니 방문 체크를 한다.
    • 1을 시작으로 DFS를 실행한다.
    • 1과 연결된 정점은 2이다. 2는 아직 방문하지 않았으니 방문 체크를 한다.
    • 2를 시작으로 DFS를 실행한다.
    • 2와 연결된 정점은 0이다. 0은 아직 방문하지 않았으니 방문 체크를 한다.
    • 0과 연결된 정점은 1이다. 1은 이미 방문을 하였으니 방문하지 않는다.
    • DFS는 종료되고, 방문체크 된 곳이 0에서 이동 가능 한 정점이다.
  • 1을 시작으로 DFS를 실행한다.
    • 이하 위와 같다.
  • 2를 시작으로 DFS를 실행한다.
    • 이하 위와 같다.
Read more
Posted Updated Algorithm

최대상금

풀이

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD&categoryId=AV15Khn6AN0CFAYD&categoryType=CODE

  • 모든 경우의 수 완전 탐색을 하려고 하였다.
  • 겹치는 부분이 있기때문에, 방문체크 배열을 만들었다.
  • 바꿀 기회가 남아 있으면 다시 재귀 함수를 호출하여 탐색을 한다.
  • 계속 오답.
  • 많은 시간을 투자했지만 풀지 못하였다.
  • 다시 풀어봐야함.

해결

  • 결국 구글링을 하였다.
  • 해결의 핵심은
    • 같은 횟수에, 같은 숫자를 탐색하는지 체크하는 배열을 두는 것이다.
  • 같은 횟수에, 해당 숫자를
    • 탐색하지 않았으면, 탐색을 시작하고
    • 탐색을 이미 했으면, 계속해서 반복문을 돌린다
Read more
Posted Updated Algorithm

그래프

  • 그래프

    • 자료구조의 일종
    • 정점(node, vertex)
      • 주로 번호가 써있음
    • 간선(edge) : 정점 사이 연결
    • 그래프 G =(V,E)로 나타냄

  • 그래프를 저장하는 방법

    • 인접 행렬
      • 정점 개수를 v라고 할때,
      • v 제곱 크기의 인차원 배열 이용
      • a[i][j]=1
        • i에서 j 로 가는 간선이 있으면
      • a[i][j]=0
        • i에서 j 로 가는 간선이 없으면
      • a[i][j] = w
        • i에서 j로의 간선 가중치가 w 이면
      • 없는 간선도 저장하기 때문에 자주 사용하지 않는 방법
      • 쉬운 문제 풀 때 주로 사용
    • 인접 리스트
      • 링크드 리스트를 이용해서 구현
      • a[i] = i와 연결된 정점이 링크드리스트 형태로 저장
      • a[1] : 2, 5
        • 1과 연결된 정점이 2, 5
      • 링크드 리스트는 구현하는데 시간이 오래걸림
        • 그래서, vector / arraylist로 함
      • 가중치가 있으면
        • 정점과 가중치를 같이 저장
        • a[1] : (2,2), (5,7)

  • 그래프의 탐색

    • 목적 : 모든 정점을 한 번씩 방문

    • 깊이 우선 탐색 (DFS)

      • 최대한 깊숙히 많이 감
      • 스택 사용
      • 스택을 이용해서 갈수 있는 만큼 많이 가고
      • 갈 수 없으면 이전 정점으로 돌아감 (스택에서 pop해서)
      • check라는 배열이 필요함
        • 0 : 아직 방문 X
        • 1 : 방문 O
      • 갈 수 있는 정점이 여러개면
        • 번호가 작은 것부터
      • pop 계속하다가 스택이 비면 탐색 종료
      • 구현
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      void dfs(int x){

      	//방문 했다고 체크
          check[x] = true;
          
          //a[x] : x와 연결된 정점들이 저장되어 있음
          for(int i=0; i<a[x].size; i++){
          
          	//x와 연결된 정점
              int y = a[x][i];
              
              //방문하지 않았으면 방문
              if(check[y] == false){
                  dfs(y);
              }
          }
      }

      ​

    • 너비 우선 탐색 (BFS)

      • 최대한 넓게 가는 것
      • 큐 사용
      • 모든 가중치가 1이면 최단 거리 찾는 알고리즘
      • 큐를 이용해서 아직 방문하지 않았고, 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
      • 큐에 넣을 때 방문했다고 체크
      • check라는 배열이 필요함
        • 0 : 아직 방문 X
        • 1 : 방문 O
      • 구현
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      queue<int> q;
      check[1] = true; q.push(1);

      while(!q.empty()){
          int x = q.front(); q.pop();
          printf("%d " , x);
          for(int i=0; i<a[x].size; i++){
              int y = a[x][i];
              if(check[y] == false){
                  check[y] = true; q.push(y);
              }
          }
      }

      ​

Read more
Follow

Recents

Categories

×