[BOJ/백준] 1303. 전투 (Python)

🔎 문제

🔗 백준 1303번 전투

💡 풀이

BFS, DFS로 풀 수 있는 문제이다. 2667 단지번호붙이기처럼 인접한 것이 몇개인지 모든 노드를 탐색하면 된다.

모든 노드 탐색

for i in range(m):
    for j in range(n):
        if graph[i][j] != 'visited':
            if graph[i][j] == 'W':
                white += bfs(i, j, 'W')**2
                # dfs: white += dfs(i, j, 'W', 1)**2
            else:
                blue += bfs(i, j, 'B')**2
                # dfs: blue += dfs(i, j, 'B', 1)**2

모든 노드에 대해 for문을 돌며 탐색을 진행한다. 방문하지 않았을경우에만 DFS,BFS를 수행하며, 해당 노드가 ‘W’라면 white의 카운트를, ‘B’라면 blue의 카운트를 중가시킨다. 이때 힘은 인접한 수의 제곱과 같으므로 결과를 제곱하여 더해준다.

DFS

def dfs(x, y, std, count):   
    graph[x][y] = 'visited'
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if graph[nx][ny] != 'visited' and graph[nx][ny] == std:
                count = dfs(nx, ny, std, count + 1)
    return count

일반적인 DFS에서 크게 벗어나지 않는다.

현재 노드에서 상,하,좌,우를 모두 탐색하는데 범위에 벗어나지 않을때만, 그리고 또 방문하지 않았을때 탐색한다.

이 문제에서 추가로 설정한 것은 ‘std`인데, 위의 코드에서 해당 노드가 W인지 B인지 기준을 인자로 함수에 넘겨줬다.

std와 현재 방문하려고 하는 노드의 값이 일치할 경우에만 카운트를 증가시키며 dfs탐색을 계속한다.

범위를 벗어나거나 인접한 노드의 값이 더이상 같지 않으면 count를 리턴하고 white나 blue의 값에 더해지게 된다.

BFS

def bfs(i, j, std):
    Q = deque()
    Q.append((i, j))
    graph[i][j] = 'visited'
    count = 0
    
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] != 'visited' and graph[nx][ny] == std:
                    graph[nx][ny] = 'visited'
                    Q.append((nx, ny))
                    count += 1
    return count + 1

DFS랑 똑같다! 다른 분들 풀이에는 방문에 -1 이나 다른 값을 넣어주셨던데 나는 문자열 배열에 다른게 들어가는게 뭔가 찝찝해서 문자열을 넣어주었다.

DFS랑 BFS중 무엇을 선택하든지 상관 없지만, 이 문제의 경우엔 BFS가 더 빠르다. 50ms 씩이나 차이가 난다. 정확한 시간은 📃소스코드아래에 첨부해 놓았다.

사실 이유는 잘 모르겠는데.. 탐색해야 하는 그래프가 100*100 밖에 안되어서 인것 같기도 하다.

📃 소스코드

import sys
from collections import deque
input = sys.stdin.readline

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

n, m = map(int, input().split())
graph = [list(input().strip()) for _ in range(m)]

def dfs(x, y, std, count):   
    graph[x][y] = 'visited'
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if graph[nx][ny] != 'visited' and graph[nx][ny] == std:
                count = dfs(nx, ny, std, count + 1)
    return count

def bfs(i, j, std):
    Q = deque()
    Q.append((i, j))
    graph[i][j] = 'visited'
    count = 0
    
    while Q:
        x, y = Q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < m and 0 <= ny < n:
                if graph[nx][ny] != 'visited' and graph[nx][ny] == std:
                    graph[nx][ny] = 'visited'
                    Q.append((nx, ny))
                    count += 1
    return count + 1

white, blue = 0, 0
        
for i in range(m):
    for j in range(n):
        if graph[i][j] != 'visited':
            if graph[i][j] == 'W':
                white += bfs(i, j, 'W')**2
                # dfs: white += dfs(i, j, 'W', 1)**2
            else:
                blue += bfs(i, j, 'B')**2
                # dfs: blue += dfs(i, j, 'B', 1)**2
                
print(white, blue)

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️