알고리즘!/Graph25 [C] 1697: 숨바꼭질 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다. 그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다. 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다. 또 queue[1000000][.. 2023. 8. 23. [C] 11403: 경로 찾기 문제는 정점 (i,j)에 대해서 i에서 j로 가는 길이가 양수인 경로가 있는지 확인하는 프로그램을 짜야한다. 여기서 알아야할 알고리즘은 Floyd's Algorthim으로 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우' 사용이 가능한 알고리즘이다. 2차원 배열에 저장을 하며 노드의 개수가 N개라고 할 때 N번만큼의 단계를 반복하여 리스트를 갱신하기 때문에 DP라고 볼 수도 있다. 이 알고리즘의 점화식은 Dab=min(Dab,Dak+Dkb)이지만 이 문제를 풀 때는 최단 경로가 아닌 경로가 있는지 확인만 하면 되기 때문에 코드가 조금 다를 수 있다. 그리고 이 점화식의 시간복잡도는 O(n^3)이다. #include #include int graph[101][101]; int mai.. 2023. 8. 23. [C] 21736: 헌내기는 친구가 필요해 간단하게 풀 수 있는 문제였다. X가 벽이고 O로 지나갈 수 있으며 P를 만날때 people++을 해주면 된다. 그리고 결국 그래프를 순회만 하면 되기 때문에 Depth-first를 이용해 풀어주었다 #include #include char graph[601][601]; int visit[601][601]; int people=0; int x_coordinate[4]={0,0,1,-1}; int y_coordinate[4]={1,-1,0,0}; void dfs(int x,int y,int x_max,int y_max) { for(int i=0;i 2023. 8. 23. [C] 14940: 쉬운 최단거리 전형적인 BFS 문제로 각 목표지점까지의 거리를 출력하면 된다. 이때 각 거리를 저장하는 배열은 visit를 이용하였고 queue를 이용하여 bfs를 구현하였다. 주의해야할 점은 1.거리를 계산하기 위해 queue[2][] 부분을 거리를 위한 공간으로 할당하였고 queue[2][rear]=queue[2][front]+1; 를 통해 거리를 구할 수 있다. 2. 2가 있던 자리를 visit 배열에서 1로 할당했기 때문에 마지막에 출력하는 부분에서 0이 출력하도록 바꿔야한다. 이건 꼭 좀 잘하자! 맨날 풀었던 문제인데 bfs 구현하는데 이상한 곳에서 시간이 걸렸다. 특히 이번에는 front와 rear을 모두 1로 초기화해놓고 while문 들어가는 조건을 front 반복문 들어가는 조건과 다차원배열 index .. 2023. 8. 21. 이전 1 2 3 4 5 6 7 다음