[Python] 백준 1303번 : 전쟁 - 전투

https://www.acmicpc.net/problem/1303

---

 

🚩DFS 코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(y, x, color) :
    
    global cnt

    if x < 0 or x >= N or y < 0 or y >= M:
        return 0
    
    if check[y][x] == False and graph[y][x] == color:
        
        check[y][x] = True
        cnt += 1
        
        for i in range(4):
            dfs(y + dy[i], x + dx[i], color)
            
        return cnt
    
    return 0        
        
cnt = 0
cntW = 0
cntB = 0
N, M = map(int, input().split())
graph = [list(input()) for _ in range(M)]
check = [[False]*N for _ in range(M)]

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

for i in range(M):
    for j in range(N):
        
        if graph[i][j] == "W":
            cntW += dfs(i, j, "W")**2
            cnt = 0
            
        if graph[i][j] == "B":
            cntB += dfs(i, j, "B")**2
            cnt = 0
            
print(cntW, cntB)

 

• DFS는 재귀함수를 활용하기 때문에 cnt 변수를 함수 안에서 정의하면 dfs()가 새롭게 호출될 때마다 초기화된다.
• '음료수 얼려 먹기' 문제 처럼 한 덩어리를 탐색하고 나면 cnt를 0으로 초기화 시켜 새롭게 진행한다.
• 좌표에서의 (x, y)와 리스트 값을 불러올 때 [y][x]를 조심
• sys.setrecursionlimit() 으로 재귀함수 횟수를 설정

 

🚩BFS 코드

처음 코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(y, x, color) :
    
    queue = deque()
    queue.append((y, x))
    check[y][x] = True
    cnt = 1
    
    while queue:
        y, x = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            
            if check[ny][nx] == True:
                continue
            
            if check[ny][nx] == False and graph[ny][nx] == color:
                check[ny][nx] = True
                queue.append((ny, nx))
                cnt += 1
    
    return cnt


cntW = 0
cntB = 0
N, M = map(int, input().split())
graph = [list(input()) for _ in range(M)]
check = [[False]*N for _ in range(M)]

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

for i in range(M):
    for j in range(N):
        
        if graph[i][j] == "W":
            cntW += bfs(i, j, "W")**2

        if graph[i][j] == "B":
            cntB += bfs(i, j, "B")**2
            
print(cntW, cntB)

 

 

• 결과가 144 72가 나와서 어디가 잘못됐는지 찾아보니 43번 째 줄 for i, j 반복문이 문제였다.
  이미 같은 편으로 한 덩어리가 방문 처리 되었을 때, 해당 i, j를 bfs 처리 하면 bfs 함수 내에 1로 설정된 cnt가 return 되면서 더해지는 것이었다.
  
  이미 방문된 곳이면 아예 bfs()가 안 돌아가게 처리해야 했다. bfs() 함수 내에 처리하거나 for i, j 반복문에서 처리하거나 해야했다.

 

최종 코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(y, x, color) :
    
    queue = deque()
    queue.append((y, x))
    check[y][x] = True
    cnt = 1
    
    while queue:
        y, x = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            
            if check[ny][nx] == True:
                continue
            
            if check[ny][nx] == False and graph[ny][nx] == color:
                check[ny][nx] = True
                queue.append((ny, nx))
                cnt += 1
    
    return cnt


cntW = 0
cntB = 0
N, M = map(int, input().split())
graph = [list(input()) for _ in range(M)]
check = [[False]*N for _ in range(M)]

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

for i in range(M):
    for j in range(N):
        
        if check[i][j] == False and graph[i][j] == "W":
            cntW += bfs(i, j, "W")**2

        if check[i][j] == False and graph[i][j] == "B":
            cntB += bfs(i, j, "B")**2
            
print(cntW, cntB)

 

• for i, j 반복문에 방문하지 않은 곳만 bfs를 돌리게 수정했다.
• dfs, bfs 문제를 풀면 가로, 세로를 뜻하는 N, M 때문에 index error가 자주 발생하고 이를 생각하느라 머리가 많이 아프다. xy 그래프에서 (x, y) 좌표는 x는 열, y는 행을 의미하지만 리스트 표현에서 [x][y]는 x는 행, y는 열을 나타낸다.
  
  그냥 함수 입력 값으로 ()가 있는 거지만 왜인지 문제 풀 때 이게 헷갈렸다. (x, y) 라는 좌표는 우리에게 익숙한 xy그래프의 좌측 맨아래가 (0, 0)으로 시작점으로 인지하지만 리스트에서는 좌측 맨위가 시작점으로 개념적으로 차이가 있다.
  
  for i, j 반복문에서도 for i in range(M)이 먼저 나와 행을 설정하고 for j in range(N)이 다음으로 열을 설정한다. 습관적으로 N, M으로 반복문을 짜면 문제 의도와 다르게 코딩이 되는 것이다.
  
  그래서 bfs() 함수에 index를 입력할 때도 (행, 열)을 주고자 수정했다. 습관적으로 (x, y)를 입력하는 것이 아니라 (y, x)를 입력하고 queue에도 일관성과 가독성을 위해 (y, x)를 append 했다. y가 행이고 x가 열이니까.