심플 이즈 베스트

글

라벨이 C플플인 게시물 표시

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

4월 14, 2016

출발점, 도착점 사이의 최단 경로를 알아내는 알고리즘, 각 꼭지점은 도시를 나타내고 변은 도로의 길이를 나타날 때, 도시간 최단경로 찾기가 문제이다 최단 경로 찾기에선 가장 간단한 문제 이기도 할 것이다. 일단 5개의 도시로 고정되어있고, -1은 갈 수 없는 거리 0은 자기 자신을 표현한다. 알고리즘을 대략적으로 설계하면, for i -> 0 , 5 , 1 [시작도시][i]로 전체를 검사한다. 완전탐색이지만, 예외조건을 둔다 0과 -1을 제외하고, isVisit을 도시크기만큼 2차원 배열을 같이 두어 방문 체크를 한다. 그리고 최소값만을 Return하는 형식을 취하면 될 것 같다. 도시를 출력하고자 한다면, vector를 따로 두어, 경로를 push_back 하면 될 것 같긴하다. 테스트 케이스 및 자료는 [알고리즘 자료] 2-1 을 보시면 있습니다. #include #include using namespace std; int city[5][5] = { 0, }; bool isVisit[5][5] = { false, }; bool isFinal = false; bool isPossiblePath(int val) { if (val == 0 || val == -1) return false; return true; } void VisitCheck(int src, int dst) { isVisit[src][dst] = true; } void VisitUnCheck(int src, int dst) { isVisit[src][dst] = false; } int Dijkstra(int src,int dst,int fDst,int path) { path = path + city[src][dst]; if (dst == fDst) return path; // 하나의 경로를 찾은 것 int result = 9999; for (int i = 0; i 추...

[알고리즘 자료] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

4월 14, 2016

구성되는 test.txt파일은 test.txt 0 3 0 5 8 -1 -1 -1 0 1 4 2 -1 -1 0 3 2 4 4 -1 0 1 -1 -1 2 1 0 로 구성되며 그림으로 나타내면, 첫째 줄 0은 출발도시, 3은 도착 도시이고, -1은 갈 수 없는 경로, 0 은 자기자신을 의미한다. 이를 토대로 결과 값은 출력 예로는 위 그림과 같이 출력된다. 소스코드는 [알고리즘] 2-1을 보시면 구현 되어있습니다. 추가로 읽으면 좋을 것

[알고리즘] 1. [C/C++] 4방향 체인코드를 이용한 논 크기 측정 문제

4월 13, 2016

알고리즘 문제 공부를 하고 있는데, 정리하여 공부겸 포스팅 할려 합니다. '논 그룹묶기 문제' 이며, 0은 논이아니고 1은 논입니다. 2차원 배열 nxn으로 구성되어있으며, test.txt의 첫 줄에는 테스트 케이스 숫자 다음 줄 부터는 nxn의 배열 크기 , 배열 값 순으로 되어있는 것을 읽으면 됩니다. 이 후 체인코드로 그룹핑된 갯수와 각 그룹들의 크기를 출력하는 문제입니다. ChainCode를 구현하는 문제로서, 4방향이지만, 여기서 대각선만 추가하면 8방향 체인코드 또한 구성됩니다. test.txt는 '알고리즘 자료' 카테고리의 첫번째에 답과 함께 올려 놓았습니다. 다음은 구현 코드이며, 알고리즘으로는, 모든 배열 인덱스에 접근하지만, 이미 그룹화 된 값과 0은 제외를 하고, 방문 할 때마다 그룹 값을 넣고, 그룹화가 끝나면, GroupNum을 증가시켜, 다시 시작하는 방법입니다. 값을 얻을 수 있습니다. 일종의 완전 탐색이지만, 예외조건이 있기에, 모든 곳을 탐색하진 않습니다. 아래 코드에서, 대각선 조건만 추가한다면, 8방향 체인코드로 구성됩니다. #include #include using namespace std; class NoN{ public: int size; }; NoN InitialNoN(int size) { NoN mData; mData.size = size; return mData; } bool IsOutBoard(int arrSize, int y, int x) { if (y = arrSize || x >= arrSize) return true; return false; } bool IsZeroOrGroupCheck(int y, int x, int **board) { if (board[y][x] != 1) return true; return false; } int...

이 블로그 검색

심플 이즈 베스트

글

우연과 필연의 교차로에서: 삶의 이유를 해부하다

[알고리즘] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

[알고리즘 자료] 2-1. [C/C++] 다익스트라를 활용한 최단 경로찾기

[알고리즘] 1. [C/C++] 4방향 체인코드를 이용한 논 크기 측정 문제

이 블로그의 인기 게시물

윤석열 계엄령 선포! 방산주 대폭발? 관련주 투자 전략 완벽 분석

대통령 퇴진운동 관련주: 방송·통신·촛불수혜주 완벽 분석

키움 OPEN API MFC 개발 (1)