백준 14716(현수막) - 파이썬(Python),자바(Java) - DFS(재귀함수),sys.setrecursionlimit(10**6),BFS

14716번: 현수막

* 재귀함수 문제 시에는 sys.setrecursionlimit(10**6)을 상단에 적어준다. 파이썬의 기본 재귀 깊이 제한이 1000으로 작은 편이기 때문에 런타임 에러 발생한다.

graph=[]
for i in range(m):
    graph.append(list(map(int,sys.stdin.readline().split())))

graph=[list(map(int,sys.stdin.readline().split())) for _ in range(m)]

 

둘은 동일하다.

1.  DFS로 푼 경우

 

스택, 큐, 재귀함수, DFS

1-1)  Python(파이썬으로 푼경우)

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드

m,n=map(int,sys.stdin.readline().split())
graph=[]
for i in range(m):
    graph.append(list(map(int,sys.stdin.readline().split())))

def dfs(x,y):#행,열
    if x<=-1 or x>=m or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        dfs(x-1,y)
        dfs(x-1,y-1)
        dfs(x-1,y+1)
        dfs(x,y-1)
        dfs(x,y+1)
        dfs(x+1,y)
        dfs(x+1,y-1)
        dfs(x+1,y+1)
        return True
    return False

result=0
for i in range(m):
    for j in range(n):
        if graph[i][j]==1:
            dfs(i,j)
            result+=1

print(result)

import sys
sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드

m,n=map(int,sys.stdin.readline().split())
graph=[list(map(int,sys.stdin.readline().split())) for _ in range(m)]

dx=[-1,-1,-1,0,0,1,1,1]
dy=[1,0,-1,1,-1,1,0,-1]

def dfs(x,y):#행,열
    if x<=-1 or x>=m or y<=-1 or y>=n:
        return False
    if graph[x][y]==1:
        graph[x][y]=0
        for i in range(8):
            dfs(x+dx[i],y+dy[i])
        return True
    return False

result=0
for i in range(m):
    for j in range(n):
        if dfs(i,j)==True:
            result+=1

print(result)

1-2)  Java(자바로 푼경우)

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

public class Main {
    static int[][] graph;
    static int m,n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());//행
        n = Integer.parseInt(st.nextToken());//열
        graph=new int[m][n];
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<n;j++){
                graph[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int result=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(graph[i][j]==1){
                    dfs(i,j);
                    result+=1;
                }
            }
        }
        System.out.println(result);
    }
    public static boolean dfs(int x,int y){
        if(x<=-1|| x>=m || y<=-1 || y>=n){
            return false;
        }
        if(graph[x][y]==1){
            graph[x][y]=0;
            dfs(x-1,y-1);
            dfs(x-1,y);
            dfs(x-1,y+1);
            dfs(x,y-1);
            dfs(x,y+1);
            dfs(x+1,y-1);
            dfs(x+1,y);
            dfs(x+1,y+1);
            return true;
        }
        return false;
    }
}

2.  BFS로 푼 경우

BFS - duque 메서드 - Python(파이썬),Java(자바)

2-1) Python(파이썬인 경우) 

import sys
from collections import deque
#sys.setrecursionlimit(10 ** 6)  # 재귀 허용 깊이를 수동으로 늘려주는 코드

m,n=map(int,sys.stdin.readline().split())
graph=[list(map(int,sys.stdin.readline().split())) for _ in range(m)]

dx=[-1,-1,-1,0,0,1,1,1]
dy=[1,0,-1,1,-1,1,0,-1]

def bfs(x,y):#행,열
    queue=deque()
    #큐 안에 저장
    queue.append((x,y))
    graph[x][y]=0
    while queue:
        x,y = queue.popleft()
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<m and 0<=ny<n:
                if graph[nx][ny]==1:
                    graph[nx][ny]=0
                    queue.append((nx,ny))

result=0
for i in range(m):
    for j in range(n):
        if graph[i][j]==1:
            bfs(i,j)
            result+=1

print(result)

2-2) Java(자바인 경우) 

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

public class Main {
    static int[][] graph;
    static int m,n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        m = Integer.parseInt(st.nextToken());//행
        n = Integer.parseInt(st.nextToken());//열
        graph=new int[m][n];
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<n;j++){
                graph[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        int result=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(graph[i][j]==1){
                    bfs(i,j);
                    result+=1;
                }
            }
        }
        System.out.println(result);
    }
    static int[] dx={-1,-1,-1,0,0,1,1,1};
    static int[] dy={-1,0,1,-1,1,-1,0,1};
    public static void bfs(int x,int y){
        Queue<int[]> q = new LinkedList<>();
        int[] array = {x,y};
        q.offer(array);
        graph[x][y]=0;
        while (!q.isEmpty()){
            int[] tmp = q.poll();
            for(int i=0;i<8;i++){
                int nx = tmp[0]+dx[i];
                int ny = tmp[1]+dy[i];
                if(0<=nx && nx<m && 0<=ny && ny<n && graph[nx][ny]==1){
                    graph[nx][ny]=0;
                    int[] array1={nx,ny};
                    q.offer(array1);
                }
            }
        }
    }
}