-
1926. [Python]그림Python_알고리즘/Silver I 2023. 12. 9. 04:21
1. 문제
https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- DFS(깊이우선탐색)
3. 파이썬 코드
def DFS(start): stack = [start] global cnt global max_width visited[start[0]][start[1]] = True width = 1 while stack: check = stack.pop() for k in range(4): dx = direction[k][1] + check[1] dy = direction[k][0] + check[0] if 0 <= dx < M and 0 <= dy < N: # 방문하지 않고 matrix 값이 1인 경우 if not visited[dy][dx] and matrix[dy][dx] == 1: # stack에 좌표값 추가 stack.append((dy, dx)) # 방문처리 visited[dy][dx] = True # 넓이 체크 width += 1 # 반복문이 다 끝났을 경우 최대 너비 갱신 if max_width < width: max_width = width # DFS를 실행한 횟수 체크 cnt += 1 N, M = map(int, input().split()) # 방향배열 direction = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 인풋값 matrix = [list(map(int, input().split())) for _ in range(N)] # 방문처리 visited = [[False] * M for _ in range(N)] # 섬의 개수 cnt = 0 # 최대넓이 max_width = 0 for i in range(N): for j in range(M): # 방문하지 않았고 섬인경우 DFS 실행 if not visited[i][j] and matrix[i][j] == 1: DFS((i, j)) print(cnt) print(max_width)
4. 문제를 풀고난 후 생각
- 깊이 우선탐색의 기초문제와 비슷한 난이도를 가지고 있다.
- 그림의 개수를 체크하는 문제고 그림의 넓이 또한 깊이우선탐색을 진행하면서 같이 체크해주면 쉽게 풀 수 있다.
- 그림의 개수의 경우 깊이우선탐색을 몇번 시행하는지를 체크하면 되고 영역의 넓이 또한 깊이우선 탐색에서 몇개의 방문하지 않은 1을 체크하고 while 문이 끝날때 이전의 max 값과 비교하여 클 경우 갱신해주는 방식으로 문제를 풀었다.
5. 문제를 푸는데 도움이 되는 지식
- 깊이우선탐색
'Python_알고리즘 > Silver I' 카테고리의 다른 글
11279. [Python]최대 힙 (0) 2024.01.09 1946. [Python]신입 사원 (0) 2023.12.19 1342. [Python]행운의 문자열 (1) 2023.12.08 1421. [Python]나무꾼 이다솜 (2) 2023.12.07 1527. [Python] 금민수의 개수 (0) 2023.08.30