[flood fill]두더지 굴 bfs/dfs 기본 문제

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84

플러드 필 - 위키백과, 우리 모두의 백과사전

flood fill에 대해서는 차차 공부해보고

오늘 3달만에 알고리즘을 시작하면서 처음 푼 두더지 문제를 포스팅한다.

처음 싸피에서 알고리즘 시작할 때도 이 문제로 시작했던 기억이 있는데 다시 시작할 때도 이 문제다.

그 만큼 기본이라는 뜻이겠지?

이 문제는 bfs, dfs도 풀 수 있다.

 

bfs

private static void bfs(int r, int c) {

  Queue<RC> queue = new LinkedList<RC>();
  queue.add(new RC(r, c));

  map[r][c] = zipnum;
  zips[zipnum]++;// zipnum의 집 수 더하기

  while (!queue.isEmpty()) {// 큐 없을때까지
    // 현재 큐에 있는 r,c 뽑아서
    RC curr = queue.poll();
    int cr = curr.r;
    int cc = curr.c;

    for (int d = 0; d < 4; d++) {// 사방 탐색 시작
      // 큐에서 뽑은 좌표에 사방 탐색하면서
      int nr = cr + dr[d];
      int nc = cc + dc[d];
      if (!check(nr, nc)) {// 범위 벗어나면
          continue;
      }
      if (map[nr][nc] == 0) {
          continue;
      }
      if (map[nr][nc] == 1) {
        map[nr][nc] = zipnum; // 방문표시 대신
        zips[zipnum]++;
        queue.add(new RC(nr, nc));
      }
    }
  }
}

 

dfs ( stack으로 )

private static void dfs2(int r, int c) {
	Stack<RC> stack = new Stack<RC>();
	stack.add(new RC(r, c));

  while (!stack.isEmpty()) {
  	RC curr = stack.pop();
    int cr = curr.r;
    int cc = curr.c;
    for (int d = 0; d < 4; d++) {
      int nr = cr + dr[d];
      int nc = cc + dc[d];

      if (!check(nr, nc)) {
      	continue;
      }
      if (map[nr][nc] == 1) {
        zips[zipnum]++;
        map[nr][nc] = zipnum;// 방문표시
        // 여기 모르겠다
        stack.add(new RC(cr, cc));
        stack.add(new RC(nr, nc));
      }
    }
  }
}

 

dfa ( 재귀로 )

private static void dfs1(int r, int c) {
	// boolean[][] check 대신 사용하는거야
  map[r][c] = zipnum;
  zips[zipnum]++; // zipnum의 집 개수 증가

  for (int d = 0; d < 4; d++) {
    int nr = r + dr[d];
    int nc = c + dc[d];
    
    if (!check(nr, nc)) {
    	continue;
    }
    if (map[nr][nc] == 1) {
    	dfs1(nr, nc);
    }
  }
}

 

범위 확인

private static boolean check(int nr, int nc) {
  // 범위 벗어나면 false
  if (nr < 0 || nc < 0 || nr >= N || nc >= N) {
  	return false;
  }
  return true;
}

 

좌표 클래스

static class RC {
  int r;
  int c;

  RC(int _r, int _c) {
    this.r = _r;
    this.c = _c;
  }
}

 

내림차순으로 출력

// 2부터 zipnum+1	까지 정렬
Arrays.sort(zips, 2, zipnum + 1);

// 뒤에서 부터 출력
for (int i = zipnum; i >= 2; i--) {
	System.out.println(zips[i]);
}