#include <stdio.h>
int n; // 정점의 총 갯수
int map[30][30], visit[30]; // 인접 행렬과 방문 여부를 나타내는 배열
void DFS(int v)
{
int i;
visit[v] = 1; // 정점 v를 방문했다고 표시
for (i = 1; i <= n; i++)
{
// 정점 v와 정점 i가 연결되었고, 정점 i를 방문하지 않았다면
if (map[v][i] == 1 && !visit[i])
{
printf("%d에서 %d로 이동\n", v, i);
// 정점 i에서 다시 DFS를 시작한다
DFS(i);
}
}
}
int main()
{
int start; // 시작 정점
int v1, v2;
scanf("%d%d", &n, &start);
while (1)
{
scanf("%d%d", &v1, &v2);
if (v1 == -1 && v2 == -1) break; // -1과 -1이 입력되면 무한 루프 탈출
map[v1][v2] = map[v2][v1] = 1; // 정점 v1과 정점 v2가 연결되었다고 표시
}
DFS(start); // DFS 시작!
return 0;
}
===================================================================================================
#include<stdio.h>
int n, min;
int map[10][10];
int count;
/*
5
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
1 0 1 0 0
1 1 1 1 1
*/
void DFS(int x, int y, int l)
{
if (x == n - 1 && y == n - 1)
{
count++;
return;
}
map[y][x] = 0;
// 위로 이동 가능?
if (y > 0 && map[y - 1][x]) DFS(x, y - 1, l + 1);
if (y < n-1 && map[y + 1][x]) DFS(x, y + 1, l + 1);
if (x > 0 && map[y][x - 1]) DFS(x -1 , y , l + 1);
if (x < n-1 && map[y][x + 1]) DFS(x +1, y , l + 1);
map[y][x] = 1;
}
int main()
{
int i, j;
scanf("%d", &n);
min = n * n; // 모든 경로를 돌아다녀도 n * n이니, 이를 최소값으로 지정해둔다
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &map[i][j]);
DFS(0, 0, 1); // DFS 시작!
printf("최단 거리: %d\n", min);
return 0;
}
===================================================================================================
#include <stdio.h>
int n; // 입력되는 정점의 최댓값
int rear, front; // 전단과 후단을 나타내는 변수
int map[30][30], queue[30], visit[30]; // 인접 행렬과 큐와 방문 배열
void BFS(int v)
{
int i;
visit[v] = 1; // 정점 v를 방문했다고 표시
printf("%d에서 시작\n", v);
queue[rear++] = v; // 큐에 v를 삽입하고 후단을 1 증가시킴
while (front < rear) // 후단이 전단과 같거나 작으면 루프 탈출
{
// 큐의 첫번째에 있는 데이터를 제외하고 제외된 값을 가져오며, 전단 1 증가
v = queue[front++];
for (i = 1; i <= n; i++)
{
// 정점 v와 정점 i가 만나고, 정점 i를 방문하지 않은 상태일 경우
if (map[v][i] == 1 && !visit[i])
{
visit[i] = 1; // 정점 i를 방문했다고 표시
printf("%d에서 %d로 이동\n", v, i);
queue[rear++] = i; // 큐에 i를 삽입하고 후단을 1 증가시킴
}
}
}
}
int main()
{
int start; // 시작 정점을 나타내는 변수
int v1, v2;
scanf("%d%d", &n, &start);
while (1)
{
scanf("%d%d", &v1, &v2);
if (v1 == -1 && v2 == -1) break;
map[v1][v2] = map[v2][v1] = 1;
}
BFS(start); // BFS 시작!
return 0;
}
===================================================================================================
#include <stdio.h>
int n, cnt; // 맵의 크기와 카운트 변수
int map[10][10]; // 맵을 나타내는 2차원 배열
int x[100], y[100], l[100]; // 좌표와 길이를 담을 배열
// 큐에 좌표 정보와 길이를 삽입하는 함수
void enqueue(int _x, int _y, int _l)
{
x[cnt] = _x;
y[cnt] = _y;
l[cnt] = _l;
cnt++;
}
void BFS(int _x, int _y)
{
int pos = 0;
// 시작점의 좌표 정보와 길이를 큐에 삽입한다
enqueue(_x, _y, 1);
// 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
while (pos < cnt && (x[pos] != n - 1 || y[pos] != n - 1))
{
// 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
map[y[pos]][x[pos]] = 0;
// 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
if (y[pos] > 0 && map[y[pos] - 1][x[pos]] == 1)
enqueue(x[pos], y[pos] - 1, l[pos] + 1);
// 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
if (y[pos] < n - 1 && map[y[pos] + 1][x[pos]] == 1)
enqueue(x[pos], y[pos] + 1, l[pos] + 1);
// 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
if (x[pos] > 0 && map[y[pos]][x[pos] - 1] == 1)
enqueue(x[pos] - 1, y[pos], l[pos] + 1);
// 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
if (x[pos] < n - 1 && map[y[pos]][x[pos] + 1] == 1)
enqueue(x[pos] + 1, y[pos], l[pos] + 1);
// 큐의 다음 순서의 지점을 방문한다
pos++;
}
// cnt가 pos보다 크다면, 도착 지점에 무사히 도착한 것이라고 말할 수 있다.
// 위의 반복문은 도착점에 도착하게 되면 루프를 바로 빠져나오기 때문에,
// 길이를 삽입하는 큐의 마지막 요소가 최단 경로의 길이라고 할 수 있다.
if (pos < cnt)
printf("최단 경로 길이: %d\n", l[pos]);
}
int main()
{
int i, j;
scanf("%d", &n);
min = n * n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &map[i][j]);
BFS(0, 0); // BFS 시작!
return 0;
}
=================
#include<stdio.h>
int N;
int scan[30][30];
int Ndanji = 2;
int sol[1000] = { 0, };
int cnt = 1;
void danji(int x, int y)
{
scan[x][y] = Ndanji;
if (scan[x][y + 1] == 1) { cnt++; danji(x, y + 1); }
if (scan[x][y - 1] == 1) { cnt++; danji(x, y - 1); }
if (scan[x - 1][y] == 1) { cnt++; danji(x - 1, y); }
if (scan[x + 1][y] == 1) { cnt++; danji(x + 1, y); }
}
void main()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%1d", &scan[i][j]);
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (scan[i][j] == 1)
{
danji(i, j);
sol[Ndanji] = cnt;
Ndanji++;
cnt = 1;
}
}
}
int tmp;
for (int i = 0; i < Ndanji; i++)
{
for (int j = 0; j < Ndanji -1-i; j++)
{
if (sol[j] > sol[j + 1])
{
tmp = sol[j];
sol[j] = sol[j+1];
sol[j+1] = tmp;
}
}
}
printf("%d\n", Ndanji-2);
for (int i = 2; i < Ndanji; i++)
{
printf("%d\n", sol[i]);
}
}
