[BAEKJOON] 4963번 : 섬의 개수 (JAVA)

2023. 1. 1. 21:38· Algorithm
반응형

- 알고리즘 분류 : DFS

- 사용 언어 : JAVA

- 문제 요점

    - 상하좌우 뿐만 아니라, 대각선도 확인

    - DFS를 이용하여 해결

 

소스 설명은 주석을 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	// 상하좌우 대각선 확인하는데 사용하는 배열
	public static int[] xmove = {-1,1,0,0,1,1,-1,-1};
	public static int[] ymove = {0,0,-1,1,1,-1,1,-1};
	
	public static int W, H;
	public static int[][] map;
	public static boolean[][] visited;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		
		// 무한반복 
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			W = Integer.parseInt(st.nextToken());
			H = Integer.parseInt(st.nextToken());
			
			// 0 0을 입력하면 반복문 탈출
			if(W == 0 && H == 0)
				break;
			
			map = new int[H][W];
			visited = new boolean[H][W];
			
			for(int i=0; i<H; i++) {
				st = new StringTokenizer(br.readLine());
				
				for(int j=0; j<W; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			int cnt = 0;
			
			// DFS로 섬의 갯수 확인
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					
					// 방문한적 없고, 섬이면 DFS함수 진행 및 섬 갯수 추가
					if(visited[i][j] == false && map[i][j] == 1) {
						visited[i][j] = true;
						cnt++;
						DFS(i,j);
					}
				}
			}
			
			sb.append(cnt + "\n");
		}
		
		System.out.println(sb.toString());		// 결과 출력
	}
	
	// DFS
	public static void DFS(int y, int x) {
		for(int i=0; i<8; i++) {			// 상하좌우대각선 확인
			int tempY = y + ymove[i];
			int tempX = x + xmove[i];
			
			if(tempY >= 0 && tempY < H && tempX >= 0 && tempX < W) {
				if(visited[tempY][tempX] == false && map[tempY][tempX] == 1) {
					visited[tempY][tempX] = true;
					DFS(tempY, tempX);
				}
			}
		}
	}
}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 10799번 : 쇠막대기 (JAVA)  (0) 2023.01.08
[BAEKJOON] 9935번 : 문자열 폭발 (JAVA)  (0) 2023.01.07
[BAEKJOON] 9466번 : 텀프로젝트 (JAVA)  (0) 2022.12.31
[BAEKJOON] 2217번 : 로프 (JAVA)  (0) 2022.12.29
[BAEKJOON] 1026번 : 보물 (JAVA)  (0) 2022.12.29
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 10799번 : 쇠막대기 (JAVA)
  • [BAEKJOON] 9935번 : 문자열 폭발 (JAVA)
  • [BAEKJOON] 9466번 : 텀프로젝트 (JAVA)
  • [BAEKJOON] 2217번 : 로프 (JAVA)
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • 알고리즘공부
  • 자기 개발
  • 자바 공부
  • 자기개발
  • 이펙티브 자바
  • junit5
  • java 8
  • MongoDB 기초부터 실무까지
  • 이펙티브자바
  • MongoDB 공부
  • 코테 공부
  • 자바공부
  • 코틀린
  • vue3 공부
  • 자기 공부
  • JPA 공부
  • 자바 개발자를 위한 코틀린 입문
  • 코테공부
  • MongoDB with Node.js
  • 프로젝트로 배우는 Vue.js 3
  • 더 자바 애플리케이션을 테스트하는 다양한 방법
  • Oracle
  • Effective Java
  • 자바 테스팅 프레임워크
  • 전산회계 2급 준비
  • 알고리즘 공부
  • 더 자바 Java 8
  • JPA
  • 자기공부
  • Java to Kotlin

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 4963번 : 섬의 개수 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.