강승현입니다
article thumbnail
반응형

문제로이동

 

2638번: 치즈

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

www.acmicpc.net


목차

     


    문제 설명

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

    공기는 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);
    	}
    }
    
    반응형
    profile

    강승현입니다

    @CODe_

    포스팅에 대한 피드백을 환영합니다!
    피드백 작성자를 존중하며, 함께 공유하고 성장할 수 있는 기회가 되기를 기대합니다.의견이나 조언이 있다면 언제든지 자유롭게 남겨주세요!

    article prev thumbnail

    이전 글

    백준 13913 숨바꼭질4 BFS

    2021.01.09

    다음 글

    백준 9328 열쇠 BFS

    2021.01.10

    article next thumbnail
    profile on loading

    Loading...