[TIL] 백준 - 그룹 단어 체커 / 피보나치 수 5 / 전쟁 - 전투

[Today I Learned]

# 백준 - 그룹 단어 체커

문제
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

 

@solution.py

# 그룹 단어 체커

words = [input() for _ in range(int(input()))]
answer = 0

for word in words:

    group = True
    alphabet = {}

    for idx in range(len(word)-1):

        if alphabet.get(word[idx]):
            group = False
            break

        if word[idx] != word[idx+1]:
            alphabet[word[idx]] = True

    # 마지막 글자 따로 검사
    if alphabet.get(word[-1]):
        group = False

    if group:
        answer += 1

print(answer)

 

# 백준 - 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

@solution.py

import sys
sys.setrecursionlimit(10**6)

n = int(input())

def fibo(i):

    if i == 1 or i == 2:
        return 1

    else:
        return fibo(i-1) + fibo(i-2)

answer = fibo(n)
print(answer)

나 재귀 짤 줄 알지..? 생각해보려고 가볍게 도전한 문젠데, 메모리 에러가 났다.
DP로 더 효율적으로 풀 수 있을 것 같아서 다시 도전했다.

n = int(input())

dp = [0, 1]

for _ in range(n-1):
    dp = [dp[1], dp[0]+dp[1]]

print(dp[0] if n ==0 else dp[1])

 

# 백준 - 전쟁 - 전투

문제

전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다.
N명이 뭉쳐있을 때는 N2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할 것인가? 단, 같은 팀의 병사들이 대각선으로만 인접한 경우는 뭉쳐 있다고 보지 않는다.

 

@solution.py

# 전쟁 - 전투

n, m = map(int, input().split()) # n - 가로(열), m - 세로(행)
wars = [list(input()) for _ in range(m)]

visited = [[False] * n for _ in range(m)]

def dfs(team, x, y, visited, count):

    if x < 0 or x >= m:
        return count

    if y < 0 or y >= n:
        return count

    if wars[x][y] == team:
        if not visited[x][y]:
            visited[x][y] = True
    
            count = dfs(team, x+1, y, visited, count)
            count = dfs(team, x, y+1, visited, count)
            count = dfs(team, x-1, y, visited, count)
            count = dfs(team, x, y-1, visited, count)

            return count + 1
    
    return count

white, blue = 0, 0

for i in range(m):
    for j in range(n):
        if wars[i][j] == 'W' and not visited[i][j]:
            white += (dfs('W',i,j, visited, 0) ** 2)
        if wars[i][j] == 'B' and not visited[i][j]:
            blue += (dfs('B',i, j, visited, 0) ** 2) 
        
print(white, blue)

점점 BFS 문제 감도 많이 잡히고, 코드 쓰는 루틴도 잡혀가고 있다.
쉽게 생각하려고 +1, -1을 하나씩 풀어서 작성해주고 있는데, 아래와 같이 코드를 단축할 수 있다.

# 전쟁 - 전투

n, m = map(int, input().split()) # n - 가로(열), m - 세로(행)
wars = [list(input()) for _ in range(m)]

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

visited = [[False] * n for _ in range(m)]

def dfs(team, x, y, visited, count):

    if x < 0 or x >= m:
        return count

    if y < 0 or y >= n:
        return count

    if wars[x][y] == team:
        if not visited[x][y]:
            visited[x][y] = True

            for i in range(4):
                nx, ny = x + dx[i], y + dy[i]
                count = dfs(team, nx, ny, visited, count)

            return count + 1
    
    return count

white, blue = 0, 0

for i in range(m):
    for j in range(n):
        if wars[i][j] == 'W' and not visited[i][j]:
            white += (dfs('W',i,j, visited, 0) ** 2)
        if wars[i][j] == 'B' and not visited[i][j]:
            blue += (dfs('B',i, j, visited, 0) ** 2) 
        
print(white, blue)