2022.01.04

백준 1012 유기농 배추

# 1012
import sys
sys.setrecursionlimit(10**6)


def DFS(x,y):
    if 0 > x or x >= N or 0 > y or y >= M:           
        return False
    
    if arr[x][y] == 1:         
        arr[x][y] = 0                                  
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True


T = int(input())    #테스트 케이스
    
for i in range(T):
    M, N, K = map(int, input().split())
    
    arr = [[0]*M for i in range(N)]  # 배추밭의 2차원 배열
    R = 0                            # 배추흰벌레 마리 수
       
    for j in range(K):
        a, b = map(int, input().split())
        arr[b][a] = 1

    for ii in range(N):
        for jj in range(M):
            if DFS(ii,jj) == 1: # 배추밭의 좌표(0,0)부터 끝까지 확인
                R += 1
    print(R)

편법?

import sys
sys.setrecursionlimit(10**6)

서버의 재귀 깊이를 늘려주는 함수를 사용해서 간신히 풀었다.

아무래도 DFS 함수의 재귀로 불러오는 게 너무 많아서 그런 듯하다.

재귀를 줄이고 반복문을 늘리는 함수를 짜 봐야겠다.

BFS(Breadth First Search)란?

BFS란 너비 우선 탐색으로도 불리며 시작 노드부터 가장 가까운 노드들을 방문하고

멀리 떨어진 노드를 나중에 탐색하는 방법이다.

DFS가 하나의 노선을 따라 종점까지 다녀오고 다시 다음 노선의 종점까지 가는 느낌이라면

BFS는 내 친구들을 하나하나 만나고 그후에 내 친구들의 친구들을 만나는걸 반복하는 느낌이다. 

BFS의 장점

- 출발노드에서 목표노드까지 최단경로를 보장한다.

BFS의 단점

- 경로가 매우 길 경우, 많은 기억 공간을 필요하게 된다.

탐색

BFS는 선입선출인 큐(Queue) 자료구조 형태를 가졌기 때문에 우선 탐색 시작 노드를 큐에 삽입과

방문처리를 한다. 그다음 큐에서 노드를 꺼낸 후 노드의 인접 노드 중 방문처리 하지 않은 노드를

모두 큐에 삽입, 방문처리 한다. 위 과정을 반복한다.

파이썬에서는 큐 구조를 사용하기위해 collections의 deque 라이브러리를 사용한다.

from collections import deque

#2667 

N = int(input())
P = [list(map(int,input())) for i in range(N)]

def DFS(x,y):
    global R
    if 0 > x or x >= N or 0 > y or y >= N:
        return False
    
    if P[x][y] == 1:
        R += 1
        P[x][y] = 0
        DFS(x-1,y)
        DFS(x,y+1)
        DFS(x+1,y)
        DFS(x,y-1)
        return True
    return False           # 지워도 됨
        

arr = []                   # 단지 내 아파트 숫자를 저장
R = 0                      # 단지 내 아파트 숫자
for i in range(N):
    for j in range(N):
        if DFS(i,j) == 1:
            arr.append(R)
            R = 0
print(len(arr))
for i in sorted(arr):
    print(i)

DFS(Depth First Search)란?

DFS란 깊이 우선 탐색으로 불리며 그래프 탐색의 한 종류이다.

루트 노드나 지정된 노드에서 시작하여 그 노드의 최대 깊이까지 탐색한 다음

더 이상 탐색 불가능하면 부모 노드로 돌아와 다른 노드로 탐색을 진행한다.

알고리즘 진행 모습은 이렇다.

이처럼 최고 깊이까지 탐색한 다음 더 이상 진행할 곳이 없으면

부모 노드로 돌아와 노드로 탐색을 진행한다.

순서의 2, 5, 9 노드로 순서로 진행하는 것은 조건을 어떻게 주느냐에 따라 다르다.

예를 들어 노드에 주어진 값이 가장 작은 것부터 탐색하거나

큰 값부터 탐색하는지 주어진 조건에 따라 탐색 순서는 바뀔 수 있다.

DFS 알고리즘 문제는 스택자료구조나 재귀 함수를 사용한다.

이때 가장 중요한 점은 방문한 노드를 방문처리하는 것이다.

방문처리하지 않으면 같은 곳을 계속 방문할 가능성이 있다.

최근 DFS와 BFS 자료구조 문제를 풀려고 시도하는데 구현에 어려움이 있어서 

개념을 정리 후에 다시 풀어보려고 작성한 글입니다.

2021.12.29

백준 2606 바이러스

#2606

F = int(input())
C = int(input())
W = [[] for i in range(F+1)]

for i in range(C):
    a,b = map(int, input().split())
    W[a].append(b)
    W[b].append(a)

arr = []
def DFS(x):
    arr.append(x)
    for i in W[x]:
        if i not in arr:
            DFS(i)
DFS(1)    
print(len(arr)-1)            # 1을 제외 갯수를 세어야 하기 때문     

DFS 함수를 정의하는데 조금 문제가 있었다.

처음에는 return을 사용해서 재귀적으로 만들려고 했는데

오류가 뜨거나 값이 제대로 안 나오거나 그랬는데

return 할 값이 없어서 그런 듯하다.

브루트포스 알고리즘이란?

 완전 탐색법이라고도 불리는 브루트포스 알고리즘은 무차별 대입법이라고도 하며,

어떤 문제에 관해서 가능한 모든 경우의 수를 구하고 답을 찾아내는 것을 말한다.

그렇기 때문에 답이 틀릴 수는 없지만 시간 효율성 측면에서 좋지 않다.

2021.12.17 - [Algorithm] - 백준 2798 파이썬

전에 올린 백준 문제 2798_블랙잭도 브루트포스 알고리즘으로 푸는 문제이다.

문제를 풀기위해서는 나올 수 있는 세 카드 합의 경우의 수를 모두 찾고

그중에서 M보다 작으면서 가장 큰 값을 찾아내면 되는 문제다. 

조사해보면서 문제를 풀기 위해서는 여러 방법이 있다고 한다.

선형구조형으로 만들거나 BFS/DFS를 사용하거나 재귀를 이용하기도 하고 반복문으로도 풀 수 있다.

때문에 문제를 풀 때 가장 먼저 고려해야 할 것은 '모든 경우의 수를 찾아야 하는가?'인 듯하다.

2021.12.17

백준 2798 블랙잭

#2798 블랙잭 /브루트포스 알고리즘

N,M = map(int, input().split())        # 카드의 개수, 목표값
arr = list(map(int, input().split()))  # 카드에 쓰여진 수
P = []                                 # 카드 3장의 합의 모든 경우의 수


for i in range(N):
    for j in range(i+1,N):
        for ii in range(j+1,N):
            S = arr[ii]+arr[i]+arr[j]
            P.append(S)
R = M                       # M - i의 최솟값을 저장하기 위한 변수            
Q = 0                       # R의 최솟값을 가지는 Q
for i in P:
    if M - i < R and M - i >= 0:
        R = M - i
        Q = i

print(Q)

모든 경우의 수를 구하는 문제라고 한다.

목푯값인 M과 카드 3장의 합인 P의 요소 중에 그 차이가 가장 작은 게 답이라는 아이디어로 풀었다.

#2798 블랙잭 /브루트포스 알고리즘

N,M = map(int, input().split())        # 카드의 개수, 목표값
arr = list(map(int, input().split()))  # 카드에 쓰여진 수
P = []                                 # 카드 3장의 합의 모든 경우의 수


for i in range(N):
    for j in range(i+1,N):
        for ii in range(j+1,N):
            S = arr[ii]+arr[i]+arr[j]
            if S <= M:
                P.append(S)

print(max(P))

풀고 나서 더 깔끔하게 만들어봤다. 메모리랑 시간도 미세하지만 아래 코드가 더 낫다.

combinations을 import해서 푸는 방법도 있는데 그건 나중에 알았으니 이제라도 잘 기억해야지

from itertools import combinations

2021.12.16

CodeUp 3120 리모컨

# CodeUp 3120 리모컨
a,b = map(int, input().split())
B = abs(a-b)                      # 두 온도차의 절대값
R = 0                             # 반복 횟수

while B != 0:
    if B >= 10:
        B = B - 10
        R += 1
    else:
        if B > 7:
            B += 1
            R += 1
        elif B > 4:
            B = B - 5
            R += 1
        elif B > 2:
            B += 1
            R += 1
        else:
            B = B -1
            R += 1
            
print(R)

처음에 짠 코드로 a-b의 절댓값을 0으로 만들어주면 된다는 아이디어로 짰다.

근데 8,9일 때는 10을 빼주고 +1 하는 게 더 최솟값이고 5,6,7일 때는 -5를 빼주는 게 최솟값이라 

세세히 조건을 줬다.

# CodeUp 3120 리모컨
a,b = map(int, input().split())
B = abs(a-b)                      # 두 온도차의 절대값
R = B//10                         # 반복 횟수


if B%10 in [1,5]:
    R += 1
elif B%10 in [2,4,6,9]:
    R += 2
elif B%10 in [3,7,8]:
    R += 3
            
print(R)

10 미만일 때 각각 0이되는 최솟값을 구하니 1,5는 1; 2,4,6,9는 2; 3,7,8은 3이 나오길래 간단히 짜 봤다. 

근데 시간은 첫 번째 코드가 조금 더 빠르다.

2021.12.13

백준 13305 주유소

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용

while P != []:  
    sm = P.index(min(P))        # 가장 저렴한 기름값의 인덱스 
    Q = Q + P[sm]*sum(R[sm:])   # 가장 저렴한 기름값 * 이후 거리
    del P[sm:]
    del R[sm:]

print(Q)

처음 짰던 코드

반복문이 돌아가면서 리스트를 계속 확인해서 그런지 시간 초과가 떴다.

아이디어는 가장 작은 기름값이 있으면 그 뒤에 거리는 가장 작은 기름값과 거리를 곱한 

값을 할당하면 된다고 생각했다.

# 13305 주유소
N = int(input())
R = list(map(int, input().split())) # 각 도시 간 거리
P = list(map(int, input().split())) # 각 도시의 기름값
del P[N-1]                          # 의미없는 마지막 값 삭제
Q = 0                               # 총 비용
S = 1000000000                      # 기름의 초기값

for i in range(N-1):
    if S < P[i]:         # 작은 기름값이 나오면 그 기름값으로 교환
        Q = Q + S*R[i]
    else:
        S = P[i]
        Q = Q + S*R[i]
        
print(Q)

S에 10억을 할당한 이유는 기름값으로 주어질 수 있는 max값이 10억이길래 초기값으로 할당했다.

그 값을 도시의 기름값고 비교해서 S가 작으면 S와 거리를 곱해주고

S가 크면 S의 값을 P[i]값으로 바꿔준 다음 S와 거리를 곱해준다. 

반복문이지만 리스트를 한 번만 확인하면 풀린다.

2021.12.10

백준 1541 잃어버린 괄호

# 1541 잃어버린 괄호
a = list(input().split('-'))
n = 0

for i in range(len(a)):
    if i == 0:
        z = sum(list(map(int,a[i].split('+'))))
        n = z
    else:
        z = sum(list(map(int,a[i].split('+'))))
        n = n - z
        
print(n)

기초 문법의 중요성을 다시 한번 깨닫는다.

입력받아올 때 split()을 사용하고서 다음에 바보같이 '어떻게 나누지?'

이런 생각을 하고 있었다. 다시 split()을 사용하면 되는데