IT-garden

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한조건

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

나의 풀이

from collections import deque

def solution(begin, target, words):
    def bfs(s):
        de=deque()
        de.append(s)
        
        while de:
            x=de.popleft()
            if x == target:
                break
            
            for i in words:
                c =0
                for be, wo in zip(x,i):
                    if be == wo:
                        c += 1
                if c == len(x)-1 and di[i] == 0:
                    di[i]=di[x]+1
                    de.append(i)
                    
    di=dict()
    di[begin]=0
    for i in words:
        di[i]=0
    bfs(begin)
    try:
        if di[target] != 0:
            return di[target]
    except:
        return 0

1. words의 단어들을 딕셔너리에 담아주고 begin 단어로 bfs를 수행했습니다.
2. 한 개의 알파벳만 바꿀 수 있는지 확인하고 바꿀 수 있다면 바꾸고 딕셔너리의 value를 1 증가시켰습니다.
3. bfs 실행후에 target값이 words에 있고 value가 0이 아니면 거친 단계 과정의 수를 리턴하고 변환할 수 없다면 0을 리턴합니다.

프로그래머스 '단어 변환' : https://programmers.co.kr/learn/courses/30/lessons/43163

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한조건

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

나의 풀이

def solution(n, computers):
    def dfs(s):
        ch[s]=1
        for i in a[s]:
            if ch[i] == 0:
                dfs(i)

    a=[[] for i in range(n)]
    for i in range(n):
        for j in range(i,n):
            if computers[i][j] == 1:
                a[i].append(j)
                a[j].append(i)
                
    ch=[0]*n
    c=0
    for i in range(n):
        if ch[i] == 0:
            c += 1
            dfs(i)  
    return c

1. computers의 배열을 토대로 각 컴퓨터가 어디에 연결되어 있는지 저장합니다.
2. dfs를 통해 모든 점을 방문하고 네트워크의 개수를 세서 리턴합니다.

프로그래머스 '네트워크' : https://programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한조건

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

나의 풀이

def solution(numbers, target):
    a=[0]
    for i in numbers:
        b=[]
        for j in a: 
            b.append(j+i)
            b.append(j-i)
        a=b
    return a.count(target)

1. 각각의 수를 더하는 경우와 빼는 경우를 리스트 b에 넣습니다.
2. 리스트 b의 값을 리스트 a에 넣습니다.
3. numbers에 대한 모든 경우를 계산하고 target과 값이 같은 개수를 리턴합니다.

프로그래머스 '타겟 넘버' : https://programmers.co.kr/learn/courses/30/lessons/43165

문제

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.

그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.

출력

K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.

예제 입력과 출력

알고리즘 분류

BFS
DFS

정답

import sys
sys.setrecursionlimit(100000)
input= lambda : sys.stdin.readline().strip()

k=int(input())

def dfs(vert,group):
    ch[vert]=group
    for i in li[vert]:
        if ch[i] == 0:
            if dfs(i,-group) is False:
                return False
        elif ch[i] == ch[vert]:
            return False
    return True

while k:
    k -= 1
    v,e=map(int,input().split())
    li=[[] for i in range(v+1)]
    ch=[0]*(v+1)

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

    ans=True
    for i in range(1,v+1):
        if ch[i] == 0:
            if dfs(i,1) is False:
                ans=False
                break

    print('YES' if ans else 'NO')

dfs를 이용한 문제입니다.
방문하지 않은 점부터 방문합니다. 이때 점을 2개의 그룹으로 나눕니다.(그룹은 -1,1로 구분)

만약 다음 점이 이미 방문한 점이면 현재 점의 그룹과 같은지 비교합니다.
같은 그룹이면 Fasle를 리턴하고 NO를 출력하고 그렇지 않으면 계속 점을 방문합니다.
False가 나오지 않고 dfs가 끝나면 Yes를 출력합니다.

백준 알고리즘 1707번 : https://www.acmicpc.net/problem/1707

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())
li=[[]*m for i in range(n)]

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

def dfs(node,d):
    print(ch)
    global r
    ch[node]=0

    if d >= 4:
        r = 1
        return

    for i in li[node]:
        if ch[i] == -1:
            dfs(i,d+1)
            ch[i]= -1

r=0
ch=[-1]*n
for i in range(n):
    dfs(i,0)
    ch[i]=-1
    if r == 1:
        break

print(r)

친구관계가 존재하는지 안하는지는 5명의 친구가 순서대로 친구관계를 이루는지를 통해 확인할 수 있습니다.

dfs를 이용해 한 친구를 기준으로 길이가 4까지 갈 수 있는지 확인했습니다.

백준 알고리즘 13023번 : www.acmicpc.net/problem/13023

문제

지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다.

그림 1. 행의 개수가 5이고 열의 개수가 7인 2차원 배열에 저장된 빙산의 높이 정보

빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 따라서 그림 1의 빙산은 일년후에 그림 2와 같이 변형된다.

그림 3은 그림 1의 빙산이 2년 후에 변한 모습을 보여준다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 서로 연결되어 있다고 말한다. 따라서 그림 2의 빙산은 한 덩어리이지만, 그림 3의 빙산은 세 덩어리로 분리되어 있다.

한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오. 그림 1의 빙산에 대해서는 2가 답이다. 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.

입력

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.

출력

첫 줄에 빙산이 분리되는 최초의 시간(년)을 출력한다. 만일 빙산이 다 녹을 때까지 분리되지 않으면 0을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

DFS

정답

from collections import deque
import copy
import sys
input = lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]

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

k = 0 #년도

def count(a): #섬의 숫자 줄이기
    aa=copy.deepcopy(a)
    
    for i in range(1,n-1):
        for j in range(1,m-1):
            s=0
            if a[i][j] > 0:
                for z in range(4):        
                    nx = i + dx[z]
                    ny = j + dy[z]

                    if 0 <= nx < n and 0 <= ny < m:
                        if a[nx][ny] == 0:
                            s += 1

                if a[i][j] - s <= 0:
                    aa[i][j] = 0
                elif a[i][j] - s > 0:
                    aa[i][j] = a[i][j] - s
    return aa

def bfs(s1,s2): #남은 섬의 개수 구하기
    de = deque()
    de.append([s1,s2])
    ch[s1][s2]=0
    
    while de:
        x, y =de.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m:
                if ch[nx][ny] == -1 and bb[nx][ny] != 0:
                    ch[nx][ny] = 0
                    de.append([nx,ny])

while True:
    k += 1
    c=0
    ch=[[-1]*m for i in range(n)] #방문여부
    
    bb=count(a)
    
    for i in range(1,n-1):
        for j in range(1,m-1):
            if bb[i][j] > 0 and ch[i][j] == -1:
                bfs(i,j)
                c += 1
    
    a=copy.deepcopy(bb)
    if c >= 2:
        print(k)
        break
    elif c == 0: #만일 빙산이 다 녹을 때까지 분리되지 않으면 
        print(0)
        break

빙산에서 일년후에 녹은 빙산이 두 덩어리 이상으로 분리되면 괜찮지만 그렇지 않을 경우 일년후 녹은 빙산을 가지고 또 일년 빙산을 녹여야 한다는 문제가 있었습니다.
문제의 핵심은 녹은 빙산을 다시 이용하여 빙산을 녹이는 것 같은데 간단한 방법은생각이 나지 않아 해당 빙산을 복사해서 다시 이용하겠다고 생각했습니다.

python 시간초과로 PyPy3로 제출했습니다.

1. 빙산을 녹입니다.
2-1. 섬의 개수를 세서 2 이상이면 섬을 녹이는데 걸린 년도를 출력합니다.
2-2. 섬의 개수가 0이면 빙산이 모두 녹았는데 분리되지 않아 0을 출력합니다.
3. 섬의 개수가 2미만이면 1, 2의 과정을 반복합니다.

백준 알고리즘 2573번 : www.acmicpc.net/problem/2573