[BOJ] 1303. 전쟁 - 전투 (Python/그래프탐색/Silver 1)

---

[문제 링크] 👉 https://www.acmicpc.net/problem/1303

---

풀이 방법

💡 DFS, BFS 이용

 

📌 주의할 점

• 가로, 세로 확인하가

Solution

from collections import deque

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

N, M = map(int, input().split())
war = [input().strip() for _ in range(M)]
visited = [[0] * N for _ in range(M)]
W, B = 0, 0

def dfs(i, j, color):
    cnt = 1
    visited[i][j] = 1
    queue = deque()
    queue.append((i, j))
    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx = dx[k] + x
            ny = dy[k] + y
            if 0 <= nx < M and 0 <= ny < N:
                if visited[nx][ny] == 0 and war[nx][ny] == color:
                    visited[nx][ny] = 1
                    cnt += 1
                    queue.append([nx, ny])
    return cnt

for i in range(M):  # 세로
    for j in range(N):  # 가로
        if war[i][j] == "W" and visited[i][j] == 0:
            W += dfs(i, j, "W") ** 2
        elif war[i][j] == "B" and visited[i][j] == 0:
            B += dfs(i, j, "B") ** 2

print(W, B)

 

개선할 점

• dfs 함수 이름 변경
  • 함수 이름은 실제 사용 방식인 BFS를 반영하지 않으므로, bfs로 변경하는 것이 더 적절하다.
• deque.append에서 튜플 사용
  • queue.append([nx, ny]) 대신 queue.append((nx, ny))로 통일성을 유지하는 것이 좋다. 튜플은 수정 불가능(immutable)하므로, BFS/DFS에서 좌표 데이터를 다룰 때 주로 사용된다.
• 불필요한 조건 간소화
  • if war[i][j] == "W" and visited[i][j] == 0 대신 if not visited[i][j]로 시작하고, war[i][j]를 인수로 넘겨 반복되는 조건을 줄일 수 있다.
• dx, dy 정의 간소화
  • dx와 dy를 리스트로 나누기보다, 이동 방향을 (x, y) 형태로 묶으면 더 간결하다.
• 입력 처리 최적화
  • 입력값을 처리할 때 strip()은 불필요하다. input()으로 한 줄씩 읽기 때문에 공백이 포함되지 않는다.

 

개선된 코드

from collections import deque

directions = [(1, 0), (0, -1), (-1, 0), (0, 1)]

N, M = map(int, input().split())
war = [input() for _ in range(M)]
visited = [[0] * N for _ in range(M)]
W, B = 0, 0

def bfs(i, j, color):
    cnt = 1
    queue = deque([(i, j)])
    visited[i][j] = 1

    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N and not visited[nx][ny] and war[nx][ny] == color:
                visited[nx][ny] = 1
                cnt += 1
                queue.append((nx, ny))
    return cnt

for i in range(M):
    for j in range(N):
        if not visited[i][j]:
            power = bfs(i, j, war[i][j])
            if war[i][j] == "W":
                W += power ** 2
            else:
                B += power ** 2

print(W, B)

---

👩‍💻 회고

가로, 세로 때문에 IndexError를 겪었다.. 글을 잘 확인할 필요가 있다.

---