DFS BFS 문제는 dx, dy로 위치 이동을 해가며 stack이나 queue에 넣고빼기를 하면 되는 문제라 다른 문제들보다는 괜찮은 것 같다. 음료수 얼려 먹기 전체 맵에서 아이스크림 개수를 구하는 문제였다. 맵은 0과 1로 이루어져 있고 0이 길(뚫려 있는 부분), 1이 벽(칸막이)이었다. dx와 dy로 방향을 정하고 dfs 재귀함수에서 4방향 중 한 번도 방문하지 않았고 길이면 다시 dfs로 탐색한다. 이때 아이스크림 개수를 찾는 문제이기 때문에 맵 전체를 탐색해야 한다. for문으로 전체 맵에서 방문하지 않았고 길인 곳에서 dfs 함수를 호출하면 최종적으로 아이스크림 총 개수를 구할 수 있다. int g[1001][1001]; int N, M; int dx[4] = { 1,-1,0,0 }; in..
연결된 단지가 몇 개인지, 각 단지의 집이 몇 개인지 출력하는 문제 dx와 dy로 4방향을 정함 (상, 하, 좌, 우) for문으로 방문하지 않은 모든 집에서 dfs 함수를 실행함 (연결되지 않은 집은 dfs로 방문할 수 없기 때문에) dfs함수 안에서 상,하,좌,우 4 방향으로 연결된 집을 찾고 연결되어 있으면서 방문하지 않았다면 dfs 각각의 단지들의 집의 개수를 cnt로 구한 후 answer 벡터에 각각 저장 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; bool arr[26][26] = { false }; //방문 여부 확인 배열 int n[26][26]; int dx[4] = { 0,..
DFS로 풀었음 시작이 1번 정점이어서 DFS(1)을 한 후 연결된 정점이 있을 때마다 cnt++을 해줬음 cnt 값이 정답 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; bool arr[101][101] = { false }; //연결되었는지 확인하는 배열 bool dfsVisited[101] = { false }; //dfs와 bfs에서 사용할 정점 방문 여부 배열 int N, M; int cnt = 0; void DFS(int v) { //시작할 위치, 함수 내에서 출력함 dfsVisited[v] = true; for (int i = 1; i
각 정점들의 방문 여부를 확인하는 배열 visited를 사용함 인접 행렬로 그래프 구현 (bool형 배열로 연결되었는지 확인함) 양방향 간선이라서 두 정점 모두 연결되어 있다고 구현 DFS와 BFS 둘 다 방문하지 않았고 연결되어 있다면 DFS/BFS하도록 함 DFS는 재귀 함수로 구현 BFS는 queue로 구현 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; #define MAX_VERTICES 10000 bool arr[1001][1001] = { false }; //연결되었는지 확인하는 배열 bool dfsVisited[1001] = { false }; //dfs와 bfs에서 사용할 정점 방문 여부 배열 ..
그래프 vertex(정점)(node, 노드), edge(간선)으로 구성됨 트리도 그래프의 일종 두 노드가 연결되어 있음 == 두 노드는 인접함 구현 방법 인접 행렬 (Adjacency Matrix) 2차원 배열로 그래프의 연결 관계 표현함 연결된 정점은 1로, 아니면 0 (또는 무한 비용 INF) 넣기 - 무조건 2차원 배열을 만들어야 해서 불필요한 공간 필요함 인접 리스트 (Adjacency List) 연결 리스트로 그래프의 연결 관계 표현함 정점의 리스트 배열을 만들어 연결된 정점들을 배열에 넣어서 표현 연결된 정보만을 저장해서 메모리를 효율적으로 사용함 연결된 데이터 하나씩 확인해야 해서 두 노드 연결되어 있는지에 대한 정보 얻는 속도가 느림 vector G[5]; //1~5까지의 정점 가진 그래프..
