IT-garden

문제

N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

예제 입력과 출력

정답

from collections import deque

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

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

def bfs():
    de=deque()
    de.append([0,0])
    ch=[[-1]*m for i in range(n)]
    ch[0][0] = 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:
                    if a[nx][ny] >= 1:
                        a[nx][ny] += 1
                    else:
                        ch[nx][ny] = 0
                        de.append([nx,ny])
    
while True:
    bfs()
    cht = 0
    
    for i in range(n):
        for j in range(m):
            if a[i][j] >= 3:
                a[i][j] = 0
                cht = 1
            elif a[i][j] == 2:
                a[i][j] = 1
    
    if cht == 1:
        c += 1
    else:
        break

print(c)

1. bfs를 통해 인접한 칸이 치즈면 값을 1 증가하고 공기칸이면 방문확인을 해주고 이동합니다.
2. 리스트 a에서 3이상인 것은(인접한 칸에 공기가 2개 이상인 것, 1부터 시작했으니까) 치즈가 녹았으니 0으로 바꿔주고
2인 것은 인접한 칸에 공기가 1개인 것이니 1로 바꿔 그대로 치즈로 유지합니다.
3. 위의 과정을 치즈가 모두 녹을때까지 반복하여 걸리는 시간을 출력합니다.

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

문제

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력과 출력

정답

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

h,w=map(int,input().split()) #h세로 w가로
a=[list(map(int,input().split())) for i in range(h)]
b=copy.deepcopy(a) 
ch=[[-1]*w for i in range(h)]

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

li=[]

def air(s1,s2):
    de=deque()
    de.append([s1,s2])
    b[s1][s2] = -1
    
    while de:
        x,y=de.popleft()

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

            if 0 <= nx < h and 0 <= ny < w:
                if a[nx][ny] == 0 and ch[nx][ny] == -1:
                    b[nx][ny] = -1
                    ch[nx][ny] = 0
                    de.append([nx,ny])

def air2(s1,s2):
    ch=[[-1]*w for i in range(h)]
    de=deque()
    de.append([s1,s2])
    b[s1][s2] = -1
    
    while de:
        x,y=de.popleft()

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

            if 0 <= nx < h and 0 <= ny < w:
                if (b[nx][ny] == 0 or b[nx][ny] in li) and ch[nx][ny] == -1:
                    b[nx][ny] = -1
                    ch[nx][ny] = 0
                    de.append([nx,ny])
     
def cheese(s1,s2,c):
    global answer
    
    for i in range(4):
        nx = s1 + dx[i]
        ny = s2 + dy[i]

        if 0 <= nx < h and 0 <= ny < w:
            
            if b[nx][ny] in li:
                b[s1][s2] = c
                answer += 1
                break
air(0,0) 
c= 1
li.append(-1)

while True:
    c += 1
    answer=0
    for i in range(h):
        for j in range(w):
            if b[i][j] != -1 and b[i][j] not in li:
                cheese(i,j,c)
                
    li.append(c)
    one = 0
    for i in b:
        one += i.count(1)

    if one == 0:
        print(c-1)
        print(answer)
        break

    air2(0,0)

1. 입력받은 리스트 a를 b로 복사합니다.

2. 함수 air를 통해 공기(-1), 구멍(0)과 치즈(1)를 분리합니다.
3. 함수 cheese를 통해서 치즈에서 공기와 접한 곳들을 확인해 값 c를 넣어줍니다. c는 걸린시간 +1
4. 리스트 b에서의 치즈의 개수를 확인합니다.
4-1. 치즈의 개수가 없다면 치즈가 모두 녹는데 걸린 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 확인해 출력합니다.
4-2. 치즈가 아직 남아있다면 함수 air2를 통해 치즈가 녹으면서 늘어난 곳을 확인해 공기로 바꿔줍니다.
5. 3와 4과정을 4-1이 될때까지 반복합니다.

위의 풀이과정은 비효율적인 코드입니다.

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

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
c=0
re=[]

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

def bfs():
    de=deque()
    de.append([0,0])
    ch=[[-1]*w for i in range(h)]
    ch[0][0]=0

    while de:
        x,y=de.popleft()

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

            if 0 <= nx < h and 0 <= ny < w:
                if ch[nx][ny] == -1:
                    if a[nx][ny] >= 1:
                        a[nx][ny] += 1
                    else:
                        ch[nx][ny] = 0
                        de.append([nx,ny])

while True:
    bfs()
    cht = 0
    cou=0
    
    for i in range(h):
        for j in range(w):
            if a[i][j] >= 2:
                a[i][j] = 0
                cou += 1
                cht = 1
                
    if cht == 1:
        c += 1
        re.append(cou)
    else:
        break

print(c)
print(re.pop())

1. bfs를 통해 인접한 칸이 치즈면 치즈를 1 증가하고 공기칸이면 방문확인을 해주고 이동합니다.
2. 리스트 a에서 2이상인 것은 치즈가 녹았으니 0으로 바꾸고 해당 시간에 녹인 치즈의 수를 구해 리스트에 저장합니다.
3. 위의 과정을 치즈가 녹을때까지 반복하고 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 구해 출력합니다.

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

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

입력

첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

예제 입력과 출력

알고리즘 분류

DFS
백트래킹

정답

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

r,c=map(int,input().split())
a=[list(map(lambda x : ord(x)-65, input())) for i in range(r)]
ch=[0] * 26 # 26은 알파벳 개수

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

def dfs(x, y, z):
    global answer
    answer=max(answer, z)

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

        if 0 <= nx < r and 0 <= ny < c and ch[a[nx][ny]] == 0:
                ch[a[nx][ny]] = 1
                dfs(nx, ny, z+1)
                ch[a[nx][ny]] = 0

answer=1
ch[a[0][0]] = 1
dfs(0, 0, answer)

print(answer)

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

입력받은 알파벳들을 아스키 코드 값으로 바꿔 저장합니다.
해당 알파벳을 거쳤는지 확인할 리스트 ch를 이용하기 위해서입니다.

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

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력과 출력

알고리즘 분류

백트래킹 

정답

from itertools import combinations

l,c=map(int,input().split())
a=sorted(input().split())
b=set('aeiou')

com=list(combinations(a,l))

for i in com:
    c=set(i)-b
    if 2 <= len(c) and l-len(c) >= 1:
        print(''.join(i))

알파벳이 중복되는 것은 없다는 것에 주의!
리스트 a에서 l개의 조합을 뽑습니다.
각 조합에서 모음의 수를 뺏을때 최소 2개의 자음이 남는지 확인하고
모음의 수가 1개 이상인지 확인하고 맞으면 출력합니다.

from itertools import combinations

l,c=map(int,input().split())
a=sorted(input().split())
com=list(combinations(a,l))

for i in com:
    num_v = 0
    num_c = 0
    for c in i:
        if c in "aeiou": #모음이 있는지 확인
            num_v +=1
        else:
            num_c +=1
    
    if num_v >=1 and num_c >=2:
        print(''.join(i))

set이 아닌 if문을 통해 모음이 있는지 확인할 수 있습니다.

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

문제 설명

프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다.

또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다.

먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요.

제한조건

• 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다.
• 작업 진도는 100 미만의 자연수입니다.
• 작업 속도는 100 이하의 자연수입니다.
• 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정합니다. 예를 들어 진도율이 95%인 작업의 개발 속도가 하루에 4%라면 배포는 2일 뒤에 이루어집니다.

입출력 예

입출력 예 설명

첫 번째 기능은 93% 완료되어 있고 하루에 1%씩 작업이 가능하므로 7일간 작업 후 배포가 가능합니다.
두 번째 기능은 30%가 완료되어 있고 하루에 30%씩 작업이 가능하므로 3일간 작업 후 배포가 가능합니다. 하지만 이전 첫 번째 기능이 아직 완성된 상태가 아니기 때문에 첫 번째 기능이 배포되는 7일째 배포됩니다.
세 번째 기능은 55%가 완료되어 있고 하루에 5%씩 작업이 가능하므로 9일간 작업 후 배포가 가능합니다.

따라서 7일째에 2개의 기능, 9일째에 1개의 기능이 배포됩니다.

나의 풀이

def solution(progresses, speeds):
    c = 0
    answer = [0] * len(progresses)
    while True:
        c += 1
        for i in range(len(progresses)):
            if progresses[i] < 100:
                progresses[i] += speeds[i]
            if progresses[i] >= 100 and speeds[i] != 0:
                progresses[i] = 100
                speeds[i] = 0
                answer[i] = c
        if 0 not in answer:
            break
    
    k = answer[0]
    cou = 1
    r = []
    for i in range(1,len(answer)):
        if k >= answer[i]:
            cou += 1
        else:
            r.append(cou)
            cou = 1
            k = answer[i]
    r.append(cou) 
    return r

1. progresses에 각 작업의 개발 속도를 더해줍니다.
2. progresses의 요소가 완료되면 걸린 날을 리스트 answer에 넣습니다.
3. 1, 2과정을 모든 작업이 완료될때까지 합니다.
4. 한번에 몇 개의 기능이 배포되는지 확인해 리스트 r을 리턴합니다.

프로그래머스 '기능개발' : programmers.co.kr/learn/courses/30/lessons/42586

문제 설명

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 CBD로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

입출력 예 설명

• BACDE: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• CBADF: 가능한 스킬트리입니다.
• AECB: 가능한 스킬트리입니다.
• BDA: B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

나의 풀이

def solution(skill, skill_trees):
    answer = 0
    skill=list(skill)

    for i in skill_trees:
        a = [-1] * len(skill)
        tree=list(i)
        
        for j, v in enumerate(skill):
            if v in tree:
                a[j]=tree.index(v)

        if sum(a) == (-1)*len(a): # 아무것도 속하지 않는 경우
            answer += 1
            continue    
        if a[0] == -1:
            continue
                            
        while True:
            if a[-1] == -1:
                a.pop()
            else:
                break
            
        b=sorted(a)
        a=list(filter((-1).__ne__ ,a))
        if a == b:
            answer += 1
        
    return answer

1. 스킬을 리스트로 만들고 스킬트리의 값들을 하나씩 리스트로 만듭니다.

2. 스킬에 있는 값이 스킬트리에 있는지 확인하고 있다면 스킬트리에서의 위치를 리스트 a에 넣습니다.

3. 스킬트리에 스킬의 값이 하나도 없다면 스킬트리가 가능한 경우이기 때문에 가능한 스킬트리의 개수 answer를 1 올려줍니다.

4. 스킬트리에 첫번째 스킬이 있어야 스킬트리가 될 가능성이 있기 때문에 첫번째 스킬트리가 있는지 확인합니다.

5. 리스트 a의 마지막 요소가 -1이면 -1을 전부 지워줍니다. 해당 위치의 스킬이 없는것으로 생각합니다.

6. 그 후 정렬한 리스트와 리스트 a에서 -1을 제거한 것을 비교합니다. (-1을 제거한 이유는 중간에 -1이 있다면 해당 스킬을 배우지 않은 것으로 간주하기 때문입니다.)

7. 두 리스트가 같으면 스킬트리의 개수 answer에 1 올려줍니다.

8. 위의 과정들을 반복한 뒤 answer를 리턴합니다.

다른 사람의 풀이

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

프로그래머스 '스킬트리' : programmers.co.kr/learn/courses/30/lessons/49993