문제:

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은 하나의 공백으로 분리되어 있다.

출력:

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

풀이방법:

https://codedrive.tistory.com/470

2636. 치즈 문제에서 조건이 하나 더 추가된 문제다. 2636 문제에 delete 배열을 이용해서 접한 횟수를 추가적으로 세서, 2 이상인 경우에만 치즈가 녹게 하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
from collections import deque
 
dx = [0,1,0,-1]
dy = [1,0,-1,0]
 
def bfs(i,j):
    queue = deque([(i,j)])
    visited = [[0 for _ in range(M)] for _ in range(N)]
    visited[i][j] = -1
    exist = False
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < N and 0<= ny < M and not visited[nx][ny]:
                if cheese[nx][ny]:
                    delete[nx][ny]+=1
                    exist = True
                else:
                    visited[nx][ny] = -1
                    queue.append((nx,ny))
    for i in range(N):
        for j in range(M):
            if delete[i][j] >= 2:
                cheese[i][j] = 0
    return exist
 
N, M = map(int,input().split())
cheese = []
for _ in range(N):
    cheese.append(list(map(int,input().split())))
    
time = 0
while True:
    delete = [[0 for _ in range(M)] for _ in range(N)]
    conti = bfs(0,0)
    if conti:
        time+=1
    else:
        break
print(time)
 cs

문제링크:

https://www.acmicpc.net/problem/2638

 

2638번: 치즈

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

www.acmicpc.net

 

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2110. 공유기 설치  (0) 2021.09.09
[BOJ]17406. 배열 돌리기 4  (0) 2021.09.08
[BOJ]2636. 치즈  (0) 2021.09.03
[BOJ] 11054. 가장 긴 바이토닉 부분 수열  (0) 2021.09.02
[BOJ]2565. 전깃줄  (0) 2021.09.01

문제:

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

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

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

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

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

입력:

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

출력:

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

풀이방법:

 일반적인 bfs와 다르게 이 치즈 문제에서는 '치즈 안에 빈 공간이 있는 경우에는 녹지 않는다' 라는 조건이 있기 때문에, 이를 신경써야 한다. 따라서 치즈를 기준으로 bfs를 하는 것이 아니라 공기를 기준으로 bfs를 수행하며 치즈를 만난 경우에 탐색을 종료하고 기록하는 방식으로 한다.

 0,0은 항상 공기이기 때문에(판의 가장자리) 이 점으로부터 시작해서 bfs를 수행하고, 모든 탐색을 마친 뒤에 한 번에 치즈를 녹이도록 한다. 이를 치즈가 모두 녹을 때까지 반복한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
from collections import deque
import sys
 
#input = sys.stdin.readline
 
dx = [0,1,0,-1]
dy = [1,0,-1,0]
 
def bfs(count):
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<= nx < N and 0<= ny < M and not visited[nx][ny]:
                visited[nx][ny] = 1
                if cheese[nx][ny]==1:
                    cheese[nx][ny] = -1
                    count-=1
                else:
                    queue.append((nx,ny))
    return count
 
def melt():
    for i in range(N):
        for j in range(M):
            if cheese[i][j] == -1:
                cheese[i][j] = 0
 
N,M = map(int,input().split())
cheese = []
count = 0
for _ in range(N):
    sub_cheese = list(map(int,input().split()))
    count += sum(sub_cheese)
    cheese.append(sub_cheese)
    
time = 0
answer = count
queue = deque()
while count:
    visited = [[0 for _ in range(M)] for _ in range(N)]
    queue.append((0,0))
    visited[0][0] = 1
    count = bfs(count)
    
    if count:
        answer = count
        
    time+=1
    melt()
    
print(time)
print(answer)
 cs

문제링크:

https://www.acmicpc.net/problem/2636

 

2636번: 치즈

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진

www.acmicpc.net

 

저작자표시 비영리 동일조건

'Algorithm > Python' 카테고리의 다른 글

[BOJ]17406. 배열 돌리기 4  (0) 2021.09.08
[BOJ]2638. 치즈  (0) 2021.09.06
[BOJ] 11054. 가장 긴 바이토닉 부분 수열  (0) 2021.09.02
[BOJ]2565. 전깃줄  (0) 2021.09.01
[BOJ]2042. 구간 합 구하기  (0) 2021.08.31

+ Recent posts

티스토리툴바