- 방법① 1) 먼저, 섬을 그룹으로 나눈다. (g[i][j] = (i,j)의 그룹 번호) 2) 그 다음 각각의 그룹에 대해서 다른 섬까지 거리를 계산한다. 3) 거리 중 가장 최소값을 구한다. * 이 방법은 각각이 그룹에 대해서 BFS 알고리즘을 수행해야 하기 때문에 느리다. #include #include using namespace std; const int MAX = 110; int a[MAX][MAX]; int g[MAX][MAX]; int d[MAX][MAX]; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0, -1,1}; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { for(int j = 0; j..
#include #include #include using namespace std; const int MAX = 1010; int map[MAX][MAX]; int check[MAX][MAX]; int dx[4] = {0,0,-1,1}; int dy[4] = {-1,1,0,0}; int main() { int m, n; scanf("%d %d", &m, &n); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { scanf("%d", &map[i][j]); if(map[i][j] == -1) check[i][j] = -1; } } bool bcheck = true; //처음 익은 토마토(시작점)를 Queue에 넣는다. queue Queue; for(i..
#include #include #include using namespace std; const int MAX = 110; int map[MAX][MAX]; int dist[MAX][MAX]; int N,M; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; int main() { scanf("%d %d", &N, &M); for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { scanf("%1d", &map[i][j]); } } /* for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { printf("%d", map[i][j]); } printf("\n"); } */ q..
- DFS #include #include using namespace std; const int MAX = 60; int w,h; int map[MAX][MAX]; int check[MAX][MAX]; int dx[8] = {-1,-1,0,1,1,1,0,-1}; int dy[8] = {0,1,1,1,0,-1,-1,-1}; void dfs(int x, int y, int cnt) { check[x][y] = cnt; for(int k = 0; k = 0 && nx = 0 && ny < w) { if(map[nx][ny] == 1 && check[nx][ny] == 0) { //pr..
- DFS //인접행렬이나 인접리스트를 만들지 않아도 //2차원 배열상에서는 한정점과 연결된 간선을 위,왼쪽,오른쪽, 아래만 탐색하면 됌. //DFS나 BFS 알고리즘을 이용해서 어떻게 이어져있는지 확인할 수 있다. //d[i][j] = (i,j)를 방문안했으면 0, 했으면 단지 번호, 마지막에는 단지번호의 갯수를 구하면됌. //집이 있는데 아직 방문하지 않았으면은 집의 개수를 늘려주고 탐색을 시작. #include #include #include #include using namespace std; const int MAX = 30; int map[MAX][MAX]; int check[MAX][MAX]; //0(방문하지않음), 1~(단지번호) int dx[4] = {-1,1,0,0}; int dy[4]..
#include #include #include #include using namespace std; const int MAX = 20010; vector myGraph[MAX]; int check[MAX]; //check[]=0(방문하지 않음), 1(빨간색, 방문함), 2(파란색,방문함) //파라미터 c를 통해 정점을 어떤 색으로 칠할지를 나타냄. void dfs(int x, int c) { check[x] = c; for(int i = 0; i < myGraph[x].size(); i++) { int y = myGraph[x][i]; if(check[y] == 0) { dfs(y, 3-c); } } } int main() { int testcase; int n,m; scanf("%d", &testca..
- DFS #include #include #include using namespace std; const int MAX = 1010; vector myGraph[MAX]; bool visited[MAX]; void dfs(int x) { visited[x] = true; for(int i = 0; i < myGraph[x].size(); i++) { int y = myGraph[x][i]; if(!visited[y]) { dfs(y); } } } int main() { int n,m; int cnt = 0; scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) { int u,v; scanf("%d %d", &u, &v); myGraph[u].push_back(v);..
- 인접 리스트 사용 #include #include #include #include #include #include using namespace std; const int MAX = 1010; int n,m,s; vector myGraph[MAX]; bool visited[MAX]; //x부터 시작하여 dfs하여 그 순서를 출력하는 함수. //단, visited에 방문 기록이 있음. void dfs(int x) { visited[x] = true; printf("%d ", x); for(int i = 0; i < myGraph[x].size(); i++) { //x와 y가 연결되어있음. int y = myGraph[x][i]; if(!visited[y]) { dfs(y); } } } void bfs(i..