https://www.acmicpc.net/problem/4963
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
4963, 섬의 개수
이번 문제는 깊이 우선 탐색을 사용해서 풀어보겠다.
# Process
input
: 섬의 넓이를 입력받으면 int 형 2차원 배열로 생성해준다.
static void input()
{
W = scan.nextInt();
H = scan.nextInt();
area = new int[H][W];
visit = new boolean[H][W];
for(int i=0; i<H; i++)
{
for(int j=0; j<W; j++)
{
area[i][j] = scan.nextInt();
}
}
}
순회
: 전체 섬의 좌표를 순회함녀서, 방문하지 않고 1로 표기된 지역에서 dfs를 호출하고 cnt 의 수를 +1 해준다.
테스트 케이스마다 cnt 를 출력해야 하기 때문에 stringBuilder 를 사용하였다.
static void pro()
{
int cnt = 0;
for(int i=0; i<H; i++)
{
for(int j=0; j<W; j++)
{
if(!visit[i][j] && area[i][j] == 1)
{
cnt++;
dfs(i,j);
}
}
}
sb.append(cnt+"\n");
}
dfs
: 기존과는 다르게 대각선까지 확인해야 하기 때문에 8개의 방향을 모두 확인하며 이동해 나아간다.
3개의 예외처리를 통과한 좌표는 dfs를 재귀 호출하며 섬의 연결좌표를 확인한다.
static void dfs(int x, int y)
{
visit[x][y] = true;
for(int k=0; k<8; k++)
{
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=H || ny>=W) continue;
if(area[nx][ny] == 0) continue;
if(visit[nx][ny]) continue;
dfs(nx, ny);
}
}
전체코드
static boolean[][] visit;
static int W,H;
static int[][] area;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1}};
static void input()
{
W = scan.nextInt();
H = scan.nextInt();
area = new int[H][W];
visit = new boolean[H][W];
for(int i=0; i<H; i++)
{
for(int j=0; j<W; j++)
{
area[i][j] = scan.nextInt();
}
}
}
static void pro()
{
int cnt = 0;
for(int i=0; i<H; i++)
{
for(int j=0; j<W; j++)
{
if(!visit[i][j] && area[i][j] == 1)
{
cnt++;
dfs(i,j);
}
}
}
sb.append(cnt+"\n");
}
static void dfs(int x, int y)
{
visit[x][y] = true;
for(int k=0; k<8; k++)
{
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if(nx<0 || ny<0 || nx>=H || ny>=W) continue;
if(area[nx][ny] == 0) continue;
if(visit[nx][ny]) continue;
dfs(nx, ny);
}
}
public static void main(String[] args)
{
while (true) {
input();
if (W == 0 && H == 0) break;
pro();
}
System.out.println(sb);
}
: )