BOJ [Silver I] 전쟁 - 전투 - 1303 (DFS 풀이)

문제 링크

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.

N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

입력

첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 병사가 한 명 있다. B는 파란색, W는 흰색이다. 당신의 병사와 적국의 병사는 한 명 이상 존재한다.

5 5
WBWWW
WWWWW
BBBBB
BBBWW
WWWWW

출력

첫 번째 줄에 당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력한다.

130 65

DFS/BFS 둘 모두로 풀 수 있는 문제

우선 DFS로 시도했고 틀린 부분이 많아서 각각 따로 포스팅

내 코드 1: 틀림👎👎

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w = 0
b = 0
def dfs_w(x, y, cnt):
    if x < 0 or x >= m or y < 0 or y >= n:
        return -1
    if graph[x][y] == 'W':
        graph[x][y] = 'X'
        cnt += 1
        cnt = dfs_w(x-1, y, cnt) if dfs_w(x-1, y, cnt) != -1 else cnt
        cnt = dfs_w(x, y-1, cnt) if dfs_w(x, y-1, cnt) != -1 else cnt
        cnt = dfs_w(x+1, y, cnt) if dfs_w(x+1, y, cnt) != -1 else cnt
        cnt = dfs_w(x, y+1, cnt) if dfs_w(x, y+1, cnt) != -1 else cnt
        return cnt
    return -1

def dfs_b(x, y, cnt):
    if x < 0 or x >= m or y < 0 or y >= n:
        return -1
    if graph[x][y] == 'B':
        graph[x][y] = 'X'
        cnt = dfs_b(x-1, y, cnt) if dfs_b(x-1, y, cnt) != -1 else cnt
        cnt = dfs_b(x, y-1, cnt) if dfs_b(x, y-1, cnt) != -1 else cnt
        cnt = dfs_b(x+1, y, cnt) if dfs_b(x+1, y, cnt) != -1 else cnt 
        cnt = dfs_b(x, y+1, cnt) if dfs_w(x, y+1, cnt) != -1 else cnt
        return cnt
    return -1

for i in range(n):
    for j in range(m):
        cnt_w = dfs_w(i, j, 0)
        print(i, j, cnt_w)
        cnt_b = dfs_b(i, j, 0)
        if cnt_w != -1:
            w += cnt_w**2
        if cnt_b != -1:
            b += cnt_w**2

print(w, b)

• 음료수 얼려먹기 예제랑 비슷하게 풀어보려고 했음

• 이 문제에서는 W, B를 구분해야 하므로, 방문한 노드는 X로 바꾸고 T/F 반환이 아니라 재귀로 돌았을 때 같은 팀인 경우 카운트 해서 그 값을 반환하고자 함

• 풀면서도 뭔가 이상하게 복잡해지는 기분인데 .. 싶었는데 역시나 결과가 이상했음

입력이 다음과 같을 때

5 2
WBWWW
WWWWW

dfs_w(0, 0, 0)의 결과 (처음 if문에 안 걸리면 < x y > 랑 그래프 출력하고 각 재귀 호출문 다음에 cnt 찍음, return cnt 전에 절취선 출력문 추가)

< 0 0 >
['W', 'B', 'W', 'W', 'W']
['W', 'W', 'W', 'W', 'W']
0 0
1
1
< 1 0 >
['X', 'B', 'W', 'W', 'W']
['W', 'W', 'W', 'W', 'W']
1 0
< 0 0 >
['X', 'B', 'W', 'W', 'W']
['X', 'W', 'W', 'W', 'W']
2
2
2
< 1 1 >
['X', 'B', 'W', 'W', 'W']
['X', 'W', 'W', 'W', 'W']
1 1
< 0 1 >
['X', 'B', 'W', 'W', 'W']
['X', 'X', 'W', 'W', 'W']
3
< 1 0 >
['X', 'B', 'W', 'W', 'W']
['X', 'X', 'W', 'W', 'W']
3
3
< 1 2 >
['X', 'B', 'W', 'W', 'W']
['X', 'X', 'W', 'W', 'W']
1 2
< 0 2 >
['X', 'B', 'W', 'W', 'W']
['X', 'X', 'X', 'W', 'W']
0 2
5
< 0 1 >
['X', 'B', 'X', 'W', 'W']
['X', 'X', 'X', 'W', 'W']
5
< 1 2 >
['X', 'B', 'X', 'W', 'W']
['X', 'X', 'X', 'W', 'W']
5
< 0 3 >
['X', 'B', 'X', 'W', 'W']
['X', 'X', 'X', 'W', 'W']
0 3
6
< 0 2 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'W', 'W']
6
< 1 3 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'W', 'W']
1 3
< 0 3 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'X', 'W']
7
< 1 2 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'X', 'W']
7
7
< 1 4 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'X', 'W']
1 4
< 0 4 >
['X', 'B', 'X', 'X', 'W']
['X', 'X', 'X', 'X', 'X']
0 4
9
< 0 3 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
9
< 1 4 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
9
9
-------------
< 0 4 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
-1
< 1 3 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
-1
-1
-1
-------------
7
-------------
< 1 3 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
-1
-------------
1
< 0 1 >
['X', 'B', 'X', 'X', 'X']
['X', 'X', 'X', 'X', 'X']
1
-------------
1

• 내가 손으로 써가면서 확인해봤는데 (1, 4)에서 상하좌우 살피고 9로 마무리 되는 것까지는 맞는데 그 이후 출력이 이해가 안 됨..!!

• (0,0)에서 dfs_w 실행되고 dfs_w(x, y+1, cnt)까지 하고 나면 'W'인 자리는 모두 'X'로 바뀌니까 거기서 끝인 줄 알았는데 다시 (0, 4)로 돌아가는 게 이해가 안 된다 ㅜㅜ 절취선이 출력됐으니까 return 되고 끝인데 왜...

내 코드 2-1: 맞았습니다

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w, b = 0, 0
cnt = 0

def dfs_w(x, y):
    global cnt
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    if graph[x][y] == 'W':
        graph[x][y] = 'X'
        cnt += 1
        dfs_w(x-1, y)
        dfs_w(x, y-1)
        dfs_w(x+1, y)
        dfs_w(x, y+1) 
        return True
    return False


def dfs_b(x, y):
    global cnt
    if x < 0 or x >= m or y < 0 or y >= n:
        return False
    if graph[x][y] == 'B':
        graph[x][y] = 'X'
        cnt += 1
        dfs_b(x-1, y)
        dfs_b(x, y-1)
        dfs_b(x+1, y)
        dfs_b(x, y+1) 
        return True
    return False


for i in range(m):
    for j in range(n):
        cnt = 0
        if dfs_w(i, j):
            w += cnt ** 2
        elif dfs_b(i, j):
            b += cnt ** 2
print(w, b)

• 일단 위에 방식 포기! 그냥 cnt 값은 global cnt로 변경해주고 return은 T/F로

• 치사하게 문제에서 가로를 n 세로를 m이라고 해놨음 그거 때문에 런타임 에러 나더라고요 문제 잘 읽어야 할 듯....

내 코드 2-2: 수정본

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w, b = 0, 0
cnt = 0

def dfs(x, y, team):
    global cnt
    if x < 0 or x >= m or y < 0 or y >= n or graph[x][y] == 'X':
        return False
    if graph[x][y] == team:
        graph[x][y] = 'X'
        cnt += 1
        dfs(x-1, y, team)
        dfs(x, y-1, team)
        dfs(x+1, y, team)
        dfs(x, y+1, team) 
        return True
    return False


for i in range(m):
    for j in range(n):
        cnt = 0
        team = graph[i][j]
        if dfs(i, j, team):
            if team == 'W':
                w += cnt ** 2
            elif team == 'B':
                b += cnt ** 2

print(w, b)

• 코드2를 함수 하나로 줄이려고 team 변수 받도록 수정

• if x < 0 or x >= m or y < 0 or y >= n or graph[x][y] == 'X':

  여기에서 graph[x][y] == 'X' 까지 체크해주지 않으면 위에랑 마찬가지로 RecursionError 뜸 (최대 재귀한도 깊이 에러)

  서치해봤을 때 아래 코드를 추가해서 재귀 깊이를 제한해주면 된다고 함

  import sys
  sys.setrecursionlimit(10**7)

• 제한을 걸어주면 에러는 안 뜨지만 아무것도 출력되지 않음

• 그래서 혹시나 해서 체크한 위치는 확인 안 하도록 graph[x][y] == 'X'를 추가해봤는데 이렇게 하니까 풀리더라 저거 하나로 큰 차이가 나는 게 아직 잘 이해는 되지 않지만 ..

다른 사람 코드: visited 배열 활용

n, m = map(int, input().split())
graph = [[c for c in input()] for _ in range(m)]
w, b = 0, 0
visited = [[False] * n for _ in range(m)]
dxy = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def dfs(x, y, team):
    global cnt
    for dx, dy in dxy:
        nx, ny = x+dx, y+dy
        if 0<=nx<m and 0<=ny<n and not visited[nx][ny] and graph[nx][ny] == team:
            visited[nx][ny] = True
            cnt += 1
            dfs(nx, ny, team)
    return 

for i in range(m):
    for j in range(n):
        cnt = 1
        team = graph[i][j]
        if not visited[i][j]:
            if team == 'W':
                visited[i][j] = True
                dfs(i, j, team)
                w += cnt ** 2
            elif team == 'B':
                visited[i][j] = True
                dfs(i, j, team)
                b += cnt ** 2

print(w, b)

• dfs로 푼 사람들 코드 구글링 해봤는데 대체로 개념에서 예제 풀었던 것처럼 visited 배열 선언해서 푸는 듯

• 이렇게 제출하고 main에서 if문이 많은 느낌이라 찾아봤는데

  w, b를 쓰지 않고 result = {'W':0, 'B': 0}를 선언해주면

  for i in range(m):
     for j in range(n):
         cnt = 1
         team = graph[i][j]
         if not visited[i][j]:
             visited[i][j] = True
             dfs(i, j, team)
             result[team] += cnt ** 2
  
  print(str(result['W']) + " " + str(result['B']) )

  이렇게 활용 가능

---

얻은 것

마음 편하게 visited를 쓰는 게 ....
왜 틀렸는지를 이해 못 하겠어서 현타 온다

bfs로 푸는 거는 따로 작성