ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 백준 1303 전쟁 - 전투
    알고리즘 2022. 8. 6. 00:38
    728x90

    문제

    전쟁 - 전투

    접근

    1. 생각해야 할 점은, 0 1 로 구분되어서 1만 구하는것이 아니라 w b 모두 각자 구해야 하는 것이다.

    2. 처음에는 w와 b에 대한 각각의 2차원 배열을 만들어서 접근을 하였다.

    3. W,B에 대해서 count를 해서 배열에 넣어서 0, 1 인덱스로 하나씩 출력했다

     

    하지만 좀 더 효율적으로 변경해 보았다 ( 위는 코드가 너무 중복된 문제가 있었다. )

    1. 위와 비슷한 방식으로 접근을 했지만 w,b에 대한 각각의 배열을 만든것이 아니라 하나의 배열로 체크하였다

    2. 또한 count를 해서 배열에 넣은것이 아니라 이중 for문을 돌면서 totalCount를 하여 바로 출력하는 방식으로 개선했다

    풀이

    # 전쟁 - 전투 -> Dfs
    m, n = map(int, input().split())
    
    board = []
    for i in range(n):
        board.append(list(map(str, input())))
    
    wCount = 0
    wTotal = 0
    
    bCount = 0
    bTotal = 0
    
    
    def dfs(x, y):
        global wCount
    
        if 0 <= x < n and 0 <= y < m and board[x][y] == 'W':
            board[x][y] = 'S'
            wCount += 1
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1)
            dfs(x, y+1)
            return True
        return False
    
    
    def dfsS(x, y):
        global bCount
    
        if 0 <= x < n and 0 <= y < m and board[x][y] == 'B':
            board[x][y] = 'S'
            bCount += 1
            dfsS(x-1, y)
            dfsS(x+1, y)
            dfsS(x, y-1)
            dfsS(x, y+1)
            return True
        return False
    
    
    for i in range(n):
        for j in range(m):
            if dfs(i, j) == True:
                wTotal += wCount ** 2
                wCount = 0
    
    for i in range(n):
        for j in range(m):
            if dfsS(i, j) == True:
                bTotal += bCount ** 2
                bCount = 0
    
    
    print(wTotal, bTotal)
Designed by Tistory.