백준 1743(음식물 피하기) - Python(파이썬) - 수학

1743번: 음식물 피하기

예제 풀이

# : 음식물 위치 

행\열	0	1	2	3	4
0	.	.	.	.	.
1	.	#	.	.	.
2	.	.	#(2)	#(1)	.
3	.	#(4)	#(3)	.

=> 음식물의 크기는 인접하여 붙어서 있는 경우 크게 된다고 했으므로 가장 큰 음식물의 크기는 4

문제 풀이

① for문으로 #(음식물이 있을 경우 ) bfs 함수 실행
② 인접한 음식물이 있을 경우 && count하지 않았을 경우 -> cnt+1 
③ count 리스트에 cnt 값 저장 후에 max 값 출력 

💻Python(파이썬)

import sys
from collections import deque

#이동할 수 있는 거리
d = [(1, 0), (0, 1), (-1, 0), (0, -1)]

#bfs 함수(행,열)
def bfs(startr, startc):
    q = deque()
    q.append((startr, startc))
    #방문 처리
    visted[startr][startc] = 1
    #음식물의 크기
    cnt = 1
    while q:
        r, c = q.pop()
        for drc in d:
            dr = r + drc[0]
            dc = c + drc[1]
            #통로안에 있을 경우
            if 0 <= dr <= n and 0 <= dc <= m:
            	#만약 방문하지 않았고(count하지 않았고) 인접한 곳에 음식물이 있을 경우
                if visted[dr][dc] == 0 and food[dr][dc] == "#":
                	#count 하였으므로 방문 처리
                    visted[dr][dc]=1
                    #인접한 음식물의 크기
                    cnt += 1
                    q.append((dr,dc))
	#리스트 count에 cnt값 append
    count.append(cnt)

n,m,k = map(int,sys.stdin.readline().split())
food = [["."]*(m+1) for _ in range(n+1)]
visted = [[0]*(m+1) for _ in range(n+1)]
count = []
for i in range(k):
    r,c = map(int,sys.stdin.readline().split())
    #음식물이 있을 경우
    food[r][c] = "#"
#for문으로
for i in range(n+1):
    for j in range(m+1):
    	#음식물이 있고 방문처리를 안 했을 경우 -> bfs 함수 실행
        if food[i][j]=="#" and visted[i][j]==0:
            bfs(i,j)


#음식물의 크기를 저장한 count 리스트에서 가장 큰 값을 출력
print(max(count))

💻Java(자바)

파이썬과 다른 점으로는 bfs 함수가 return cnt값을 하여 앞에 max 값과 비교하면서 달라진다.

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

public class Main {
    static int[][] d ={{1,0},{0,1},{-1,0},{0,-1}};
    static int N,M;
    static boolean[][] visted;
    static int[][] food;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //세로 길이
        N = Integer.parseInt(st.nextToken());
        //가로길이
        M = Integer.parseInt(st.nextToken());
        //음식물 쓰레기 개수
        int K = Integer.parseInt(st.nextToken());
        //리시트 인접한 음식물의 크기
        int max =0;
        //음식물
        food = new int[N+1][M+1];
        //음식물 count 했는지 안했는지 방문 여부
        visted = new boolean[N+1][M+1];
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            food[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())]=1;
        }
        for(int i=0;i<N+1;i++){
            for(int j=0;j<M+1;j++){
                if(food[i][j]==1 && !visted[i][j]){
                    int cnt = bfs(i,j);
                    //앞 cnt 값과 비교하여 최댓값 입력
                    if(max<cnt){
                        max = cnt;
                    }
                }
            }
        }
        System.out.println(max);
    }
    static int bfs(int startr,int startc){
        int cnt=0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {startr,startc});
        while(!q.isEmpty()){
            int[] temp = q.poll();
            for(int[] drc:d){
                int dr = temp[0]+drc[0];
                int dc = temp[1]+drc[1];
                if(0<=dr && dr<=N && 0<=dc && dc<=M){
                    if(!visted[dr][dc] && food[dr][dc]==1){
                        visted[dr][dc]=true;
                        cnt++;
                        q.offer(new int[] {dr,dc});
                    }
                }
            }
        }
        return cnt;
    }
}