백준 2638 치즈 풀이 python,java

문제로이동

2638번: 치즈

---

목차

 

---

문제 설명

하도 안풀려서 풀이를 볼까 말까 하다가 끝까지 붙잡고 풀어냈다.

공기는 0, 치즈는 1로 표시된다. 맨 가장자리는 반드시 공기층이 있다.

즉, 매 반복마다 bfs(0,0)만 돌리면 된다는 말이다!!

이미 방문한 구역을 visited로 체크해두고 공기층에 2번 노출되면 그 치즈는 없애버린다. 

그리고 반드시!! 치즈가 없어진 구역은 방문한 것으로 표기해둔다.

그렇지 않으면 그 다음 큐가 돌아갈 때 방문을 하면서 다음 턴에 없어져야 할 치즈들이 한 턴에 사라진다.

---

소스 코드

Python

입력시에 치즈 개수를 파악하게 만들었고, 공기중에 노출된 치즈(없어지는 치즈)가 생기면 해당 개수를 1씩 감소시켰다.

그리고 모든 치즈 수가 0이 되는 순간에 반복문을 break하여 출력하는 구조다.

##########################################################
import sys
from collections import deque
direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################

height,width = mii()
field = list()
chzcnt = 0	#치즈 개수
#치즈 개수 세면서 동시에 삽입
for _ in range(height):
    tmp = lmii()
    chzcnt+=sum(tmp)
    field.append(tmp)

def bfs():
    global chzcnt
    visited = [[-1]*width for _ in range(height)]
    visited[0][0]=0
    q = deque([[0,0]])
    while q:
        x,y = q.popleft()
        for dx,dy in direction:
            nx,ny = x+dx,y+dy
            if 0<=nx<width and 0<=ny<height:
                if visited[ny][nx]==-1 and field[ny][nx]==0:#첫방문,공기층
                    visited[ny][nx]=0
                    q.append([nx,ny])
                elif field[ny][nx]==1:
                    visited[ny][nx]+=1#0,1
                    if visited[ny][nx]==1:
                        chzcnt-=1
                        field[ny][nx]=0
                        visited[ny][nx]=0
cnt=0
while chzcnt:
    bfs()
    cnt+=1
print(cnt)

Java8(21.02.03 추가)

main 메소드에서는 기본적인 입력을 처리했고 dfs 메소드를 호출합니다.

1. dfs 메소드에서는 모든 치즈가 없어질 때까지 계속해서 while문이 돌아갑니다.

2. 한 번 while문이 돌아가면 모든 움직일 수 있는 공간을 탐색합니다.

3. 이동 가능한 공간이 있다면 현재 시간(초는 매 while마다 증가) +1로 visisted에 기록을 합니다. (현재 1초라면 2초부터 방문이 가능하도록 visited에 2를 기록합니다.)

4. 또한 해당 필드에 치즈가 있다면 치즈는 없앱니다.(0으로 바꿉니다) 어차피 없애도 visited로 인해 방문이 불가능하기 때문에 다음 time에만 방문이 가능합니다.

5. 2~4 과정을 반복합니다.

6. while이 시작되면 항상 남은 치즈 갯수를 answer 변수에 저장해뒀기 때문에 마지막 while문(치즈가 없어지는 순간)이 실행될 때는 최종 치즈 갯수가 저장되어 있습니다. 이것을 main에서 출력해줍니다.

 

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int[][] field;
	static int[][] visited;
	static int answer,N,M,chzcnt;
	static Deque<Pos> dq;
	static int direction[][] = {{0,1},{1,0},{-1,0},{0,-1}};
	static class Pos{
		int x,y,time;
		public Pos(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int dfs() {
		int time = 1;
		while(chzcnt>0) {
			answer = chzcnt;
			Deque<Pos> dq = new ArrayDeque<Main.Pos>();
			dq.add(new Pos(0,0));
			visited[0][0]=time+1;
			while(!dq.isEmpty()) {
				int x = dq.peekFirst().x;
				int y = dq.pollFirst().y;
				for(int[] dpos : direction) {
					int nx = x+dpos[0];
					int ny = y+dpos[1];
					if(0<=nx && nx<M && 0<=ny && ny<N && visited[ny][nx]<=time) {
						if(field[ny][nx]==0)
							dq.add(new Pos(nx,ny));
						else if(field[ny][nx]==1) {//해당 자리에 치즈?
							field[ny][nx]=0;
							chzcnt--;	
						}
						visited[ny][nx]=time+1;//지난곳은 못가게. 다음 시간에 올 수 있게.
					}
				}
			}
			time++;
		}
		return time-1;
	}
	public static void main(String[] args) throws IOException{
		answer =0;
		st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());			
		field = new int[N][M];
		visited = new int[N][M];
		for(int i =0;i<N;i++) {
			st = new StringTokenizer(bf.readLine());				
			for(int j =0;j<M;j++) {
				field[i][j]=Integer.parseInt(st.nextToken());
				if(field[i][j]==1)chzcnt++;
			}
		}
		System.out.println(dfs()+"\n"+answer);
	}
}