DFS6 [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] 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] 10026: 적록색약 그 동안 너무 BFS로만 풀어서 오랜만에 DFS로 풀었다 사실 구역이 몇개인지 알아보는 문제들은 그래프를 다 순회하기만 되기 때문에 BFS를 쓰든 DFS를 쓰든 아무 상관이 없다. 하지만 그래프 내에서 최소로 도달하는 순서나 그래프 순회를 넓이 우선으로 해야하는 경우는 BFS를 써야한다. 사실 아직 많이 풀어보지는 못했지만 DFS로만 풀리는 문제는 보지 못해 헷갈린다면 그냥 BFS를 써야겠다. 그리고 정수를 한꺼번에 배열처럼 받을때 %1d를 사용하면 하나씩 값을 얻을 수 있는데 %1c는 그런게 없다. 항상 배열의 시작이 0인지 1인지 잘생각하면서 풀어야겠다는 생각이 들었다. 또 이 문제와 같이 그래프안의 원소의 값이 달라질때는 아예 clear()함수를 만들어 초기화 시켜주는게 더 깔끔한 것 같다. #in.. 2023. 7. 30. [C] 2667: 단지번호붙이기 이 문제는 앞서 풀었던 미로 탐색 문제와 매우매우매우 흡사하다 공통점으로는 일단 그래프 끝까지 모두 탐색을 해야하고 이걸 저정해야하며 BFS 알고리즘을 사용해서 풀어야했던 것인데 사실 DFS 알고리즘을 써도 풀렸을 것이다. 그래도 미로탐색 문제가 생각이 나서 BFS로 풀게 돠었다 BFS 알고리즘을 사용할 떄 전역 변수를 잘 사용해야하고 nx,ny를 잘 사용하여 범위를 정해 최대한 간결하면서도 이해하기 쉽게 코드를 정리하는게 중요한 것 같다. 또한 queue 배열을 사용해야하는데 아직 이에 익숙치 않아 더 공부해야겠다. 차이점으로 미로탐색 문제는 맨 마지막 좌표까지 도달하는 최단 경로를 찾는 문제였고 이번 문제는 단지를 찾아서 단지 안에 있는 아파트를 찾는 것이다. 또 다른 차이점은 여러가지 그래프가 생성.. 2023. 7. 29. 이전 1 2 다음