[파이썬] 백준 1303 : 전쟁 - 전투 (실버1)

[파이썬] 백준 1303 : 전쟁 - 전투 (실버1)

1303번: 전쟁 - 전투

---

문제

---

풀이

방향성 생각

• 군집 크기 구하기. 기본적인 BFS / DFS 문제

 

DFS

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
arr = [list(input()) for _ in range(h)]
visit = [[False]*w for _ in range(h)]

def dfs(x,y,c):
    if x<0 or y<0 or x>=w or y>=h:
        return 0
    if not visit[y][x] and arr[y][x]==c:
        visit[y][x] = True
        return 1+dfs(x-1,y,c)+dfs(x+1,y,c)+dfs(x,y-1,c)+dfs(x,y+1,c)
    return 0

info = [0,0]
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'W':
            info[0] += dfs(j,i,'W')**2
        if arr[i][j] == 'B':
            info[1] += dfs(j,i,'B')**2
print(*info)

• 재귀야 항상 하던대로, 탈출조건 적어주기. 맵 밖에 벗어나는 경우는 탐색 x
• 맵 안쪽인 경우에는 방문처리 안된 경우, 같은 색깔인 경우에만 진행.
• 출력은 언패킹으로 한 번에

BFS

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

w,h = map(int,input().split())
arr = [list(input()) for _ in range(h)]

visit = [[False]*w for _ in range(h)]
dire = [(1,0),(-1,0),(0,1),(0,-1)]

def bfs(x,y):
    
    count,color = 1,arr[y][x]
    visit[y][x] = True
    
    q = deque([(x,y)])
    while q:
        x,y = q.popleft()

        for dx,dy in dire:
            nx = x + dx
            ny = y + dy
            
            if 0<=nx<w and 0<=ny<h and not visit[ny][nx] and color == arr[ny][nx]:
                q.append((nx,ny))
                visit[ny][nx] = True
                count += 1
    return count**2

info = [0,0]
for i in range(h):
    for j in range(w):
        if not visit[i][j]:
            if arr[i][j] == 'W':
                info[0] += bfs(j,i)
            else:
                info[1] += bfs(j,i)
print(*info)

• dfs로 같은 색깔인 경우에 탐색을 진행한다.
• 맵 내부에 들어온 경우 방문하지 않은 인접한 같은색깔 노드를 탐색한다.
• count 전부 해주고, 제곱해서 리턴.
• BFS로 격자 순회하면서 방문하지 않은 노드에서 BFS 진행
• 출력은 언패킹

코멘트

기본 알고리즘 웰노운 문제들은 10분 언저리면 실수없이 푸는듯?

실수해도 실수 할만한 부분들을 알아서 디버깅도 빠르다