백준 2638번: 치즈 [JAVA]

2023. 3. 27. 02:28·개발/코딩테스트

https://www.acmicpc.net/problem/2638

 

2638번: 치즈

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로

www.acmicpc.net

 

 * 풀이

가장 바깥의 공간부터 사방을 탐색한다. 주변에 빈 공간이 있다면 다음 공간도 탐색하고 치즈를 만난다면 체크만 한다. 치즈를 두 번 만난 경우 표시를 0으로 바꿔 치즈를 없앤다. 이 반복을 치즈가 모두 사라질 때까지 반복하고 반복한 횟수를 출력한다.

 

* 코드

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

public class Main {
	static int N, M;
	static int map [][];
	static int CHEEZE;
	static int remain;
	static int cnt;
	static int dx[] = {1,-1,0,0};
	static int dy[] = {0,0,1,-1};
	static boolean isVisited[][];
	
	static boolean checkValid(int x, int y) {
		if (x<0 || x>=N || y<0 || y>=M) return false;
		else return true;
	}
	
	static void removeCheeze(int x, int y) {
		
		for (int i=0; i<4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			
			if (!checkValid(next_x, next_y)) continue; // 범위 밖일 경우 무시
			
			if (map[next_x][next_y]==1) { // 치즈
				if (isVisited[next_x][next_y]) {
					map[next_x][next_y] = 0; // 두 번 만난 경우 사라짐
					remain--; // 남은 치즈 - 1
				}
				else { // 처음 만난 경우
					isVisited[next_x][next_y] = true; // 방문 체크
				}
			}
			
			else { // 공기
				if (!isVisited[next_x][next_y]) { // 처음 만났다면
					isVisited[next_x][next_y] = true;
					removeCheeze(next_x, next_y); // 이동
				}
			}
			
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 입력 및 초기화
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int [N][M];

		for (int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j=0; j<M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j]==1) CHEEZE++;
			}
		}
		
		remain = CHEEZE;
		
		while(remain!=0) {
			isVisited = new boolean [N][M];
			removeCheeze(0,0);
			cnt ++;
		}
		System.out.println(cnt);
	}

}
'개발/코딩테스트' 카테고리의 다른 글
  • 백준 1697번: 숨바꼭질 [JAVA]
  • 백준 13923번: ABCDE [JAVA]
  • 백준 9663번: N-Queen [JAVA]
  • 정올 1828번: 냉장고 [JAVA]
로또
로또
게임 개발자 연습생의 발전 일지
  • 로또
    게임 개발 발전소
    로또
  • 전체
    오늘
    어제
    • 분류 전체보기 N
      • 개발
        • 코딩테스트
        • JAVA
        • DB
        • Unity
      • 강의 N
        • 패스트캠퍼스 0원 챌린지
        • 멋쟁이 사자처럼 유니티 부트캠프 N
      • 게임
        • 리뷰
  • 블로그 메뉴

    • 홈
    • 방명록
    • 글쓰기
  • 링크

    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    자료구조
    설탕배달
    백트래킹
    그래프
    C4D
    패스트캠퍼스후기
    Java
    최소신장트리
    직장인인강
    dfs
    한번에끝내는프론트엔드개발초격차패키지Online
    2839
    패스트캠퍼스
    완전탐색
    코딩테스트
    백준
    BFS
    환급챌린지
    트리
    그리디알고리즘
    3D웹인터랙티브
    패캠인강후기
    수강료0원챌린지
    분리집합
    패캠챌린지
    오공완
    멋쟁이사자처럼후기
    부분집합
    그리디
    직장인자기계발
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
로또
백준 2638번: 치즈 [JAVA]
상단으로

티스토리툴바