[백준] 1303 전투 파이썬

 

1303번: 전쟁 - 전투

실버1 이었고 처음에 dfs풀어서 런타임 에러가 발생했다. 그래서 bfs로 다시 풀었음.

 

DFS로 풀 때 런타임 에러가 발생하는 이유 : 

1. 스택 오버플로우

•  DFS는 재귀함수 또는 스택을 사용해 구현할 수 있다. 하지만 입력의 크기가 커지면서 재귀 호출이 너무 깊어져 스택 오버플로우가 발생할 수 있다. 
• 특히 이 문제에서는 가로 크기와 세로 크기가 최대 100이므로 재귀 호출이 깊어지는 경우가 발생할 수 있다. 

BFS로 풀어야 하는 이유 : 

1. 시간 복잡도가 더 효율적이다. 

• BFS의 시간 복잡도는 O(V+E). V는 정점. E는 간선, DFS는 시간 복잡도가 O(V+E) 이상일 수 있다. 

 

<정답코드_BFS>

#1303 전투 bfs
from collections import deque

n, m = map(int, input().split())
maps=[]
visited=[[0]*n for i in range(m)]

for i in range(m):
    li=input()
    li=list(li)
    maps.append(li)


def bfs(v,x,y,visited,maps,n,m):
    queue=deque()
    queue.append([x,y])
    count=1
    visited[y][x]=1

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

    while queue:
        x,y=queue.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]

            if 0<=nx<n and 0<=ny<m:
                if visited[ny][nx]==0 and maps[ny][nx]==v:
                    visited[ny][nx]=1
                    queue.append([nx,ny])
                    count+=1

    return count

wlist=[]
blist=[]

for i in range(m):
    for j in range(n):
        if visited[i][j]==0 and maps[i][j]=='W':
            count=bfs('W',j,i,visited,maps,n,m)
            wlist.append(count)
        if visited[i][j]==0 and maps[i][j]=='B':
            count=bfs('B',j,i,visited,maps,n,m)
            blist.append(count)
            

#위력
wlist=list(map(lambda x:x**2,wlist))
blist=list(map(lambda x:x**2,blist))

print(sum(wlist),sum(blist))

 

 

< DFS 풀이>

 

런타임에러난 코드. 근데 일단 맞긴 함. 

#1303 전투_dfs 런타임에러
n, m = map(int, input().split())
maps=[]
visited=[[0]*n for i in range(m)]

for i in range(m):
    li=input()
    li=list(li)
    maps.append(li)

def dfs(v,maps,visited,n,m,x,y):
    global count

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

    visited[y][x]=1

    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]

        if 0<=nx<n and 0<=ny<m:
            if visited[ny][nx]==0 and maps[ny][nx]==v:
                visited[ny][nx]=1
                count+=1
                dfs(v,maps,visited,n,m,nx,ny)
wlist=[]
blist=[]

for i in range(m):
    for j in range(n):
        if maps[i][j]=='W' and visited[i][j]==0:
            count=1
            dfs('W',maps,visited,n,m,j,i)
            wlist.append(count)
        elif maps[i][j]=='B' and visited[i][j]==0:
            count=1
            dfs('B',maps,visited,n,m,j,i)
            blist.append(count)

#적국의 병사 위력의 합 출력
wlist=list(map(lambda x:x**2,wlist))
blist=list(map(lambda x:x**2,blist))

print(sum(wlist),sum(blist))