알고리즘!/Graph25 [C] 11724: 연결 요소의 개수 일단 이 문제도 결국 그래프 탐색 문제이다. 최단 거리와 관계가 없고 그냥 그래프가 서로 이어져 있냐만 확인하면 되므로 Depth-first(깊이 우선탐색)을 이용하여 인접행렬을 통해 문제를 풀었다. 여기서 유일하게 주의해야 할점은 노드가 하나라도 독립적인 연결 요소가 된다는 것이다. 그렇기 때문에 인접행렬에서 자기자신에게 가는 간선도 추가해줘야 간단히 풀 수 있다. #include int graph[1001][1001]; int visit[1001][1001]; void dfs(int n, int line, int x, int y) { for(int i=1;i 2023. 8. 6. [C] 7569: 토마토 7576 토마토 문제와 거의 유사하지만 전에 문제는 2차원 배열, 이번 문제는 3차원 배열로 풀어야한다는 점에서 다르다. 전에 코드에 비해 나아진 점을 찾아보자면! 1. graph 값을 저장하면서 동시에 익은 토마토가 있는 경우에 바로 queue에 저장해뒀고 2. 몇번째 날에 익었는지를 새로운 배열로 선언하지 않고 queue 배열을 [][4]로 지정하여 0에는 z, 1에서 y, 2에는 x, 3에는 익은 날짜를 저장함으로써 가독성을 높였다. 3. 익은 토마토 개수와 토마토가 없는 자리의 개수를 따로 구함으로써 예외인 경우를 처리해줬다. 주의해야할 점을 찾아보자면! 3차원 문제이기때문에 Z,Y,X 순서를 헷갈리지 않아야하고 맨 마지막에 bfs()함수에서 return 할때 queue[rear][3]에는 아무런.. 2023. 8. 4. [C] 1389: 케빈 베이컨의 6단계 법칙 일단 인접행렬로 그래프를 저장한다음에 for문을 이용하여 언제가 베이컨 수가 가장 작은지를 확인해봤다. 나아진 점1: 처음에 bfs를 돌릴때 queue에다가 먼저 놓고 bfs함수를 호출함으로써 dfs와 bfs를 섞어쓰던 실수를 없앴다! 나아진 점2: bfs함수에서 beacon_number을 구할때 따로 배열을 만들어 몇번째에 beacon_number에 넣었는지 저장해두었는데 이번에는 beacon_number[i]=beacon_number[tmp]+1; 를 사용하여 배열 2개로 저장하던걸 1개로 저장하여 효율성을 높였다. 나아진점 3: bfs 만드는 속도가 빨라졌고 continue의 사용을 적절히 했다! 그리고 그래프에서의 최단거리를 구할 때는 항상 BFS를 쓴다는 것을 잊어버리면 안된다!! #includ.. 2023. 8. 3. [C] 10026: 적록색약 그 동안 너무 BFS로만 풀어서 오랜만에 DFS로 풀었다 사실 구역이 몇개인지 알아보는 문제들은 그래프를 다 순회하기만 되기 때문에 BFS를 쓰든 DFS를 쓰든 아무 상관이 없다. 하지만 그래프 내에서 최소로 도달하는 순서나 그래프 순회를 넓이 우선으로 해야하는 경우는 BFS를 써야한다. 사실 아직 많이 풀어보지는 못했지만 DFS로만 풀리는 문제는 보지 못해 헷갈린다면 그냥 BFS를 써야겠다. 그리고 정수를 한꺼번에 배열처럼 받을때 %1d를 사용하면 하나씩 값을 얻을 수 있는데 %1c는 그런게 없다. 항상 배열의 시작이 0인지 1인지 잘생각하면서 풀어야겠다는 생각이 들었다. 또 이 문제와 같이 그래프안의 원소의 값이 달라질때는 아예 clear()함수를 만들어 초기화 시켜주는게 더 깔끔한 것 같다. #in.. 2023. 7. 30. 이전 1 2 3 4 5 6 7 다음