×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,710명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :

 

www.acmicpc.net/problem/2636

 

2636번: 치즈

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

www.acmicpc.net

 

 

 

알고리즘 분석 :


문제 해결에 필요한 사항

1. BFS

 

 

- 가장 겉면에 있는 1을 모두 찾고

- 그다음 찾은 인덱스를 모두 지워주는 방식으로 진행하면 쉽게 해결 가능하다.

 

 

 
아래 코드에서 재미있는건 

2차원 배열을 1차원화 시켜서 list comprehension으로 리스트에서 1만 추출한 후 해당 len을 구하면 1의 개수를 구할 수 있게 된다.

flat = sum(arr, [])
lastCount = len([i for i in flat if i])

 

소스 코드 : 

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

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


def getStartQueue():
    q = []
    startq = []
    visit = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                q.append([i, j])
                break
        if len(q) != 0:
            break

    while True:
        if len(q) == 0:
            break

        y, x = q.pop(0)

        if visit[y][x]:
            continue

        visit[y][x] = 1

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

            if 0 <= nx < m and 0 <= ny < n:
                if arr[ny][nx] and not visit[ny][nx]:
                    visit[ny][nx] = 1
                    startq.append([ny, nx])
                if arr[ny][nx] == 0:
                    q.append([ny, nx])

    return startq


def eatCheese(startq):
    while True:
        if len(startq) == 0:
            break

        y, x = startq.pop(0)
        arr[y][x] = 0


lastCount = 0
lastDay = 0
while True:
    startq = getStartQueue()

    if len(startq) == 0:
        break

    lastDay += 1

    flat = sum(arr, [])
    lastCount = len([i for i in flat if i])

    eatCheese(startq)

print(lastDay)
print(lastCount)

 

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2636번] 치즈  (1) 2021.06.01
[11번] Container With Most Water  (0) 2021.05.10
[35번] Search Insert Position  (0) 2021.05.07
[1018번] 체스판 다시 칠하기  (0) 2020.03.16
[17472번] 다리 만들기 2  (0) 2020.03.14
[SwExpertAcademy] 아나그램  (0) 2020.01.04
  1. suhwanc 2021.06.01 14:27 신고

    아직도 문제 푸시는군요!! 잘 봤습니다!