-
1012. [Python]유기농 배추Python_알고리즘/Silver II 2023. 8. 19. 23:43
1. 문제
https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 512MB
- DFS(깊이 우선 탐색)
3. 파이썬 코드
import sys input = sys.stdin.readline dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] # 깊이 우선 탐색 함수 def DFS(start): stack = [] stack.append(start) visited[start[0]][start[1]] = True # stack 에 i, j 튜플 형태로 들어온 값 추출 while stack: col, row = stack.pop() # 들어온 값들의 방향배열을 탐색함 for k in range(4): x = row + dx[k] y = col + dy[k] # M, N 사이에 존재하며 방문하지 않고 1인 경우 if (0 <= x < M) and (0 <= y < N): if not visited[y][x] and matrix[y][x] == 1: # 방문 처리후 스택에 값 추가 visited[y][x] = True stack.append((y,x)) T = int(input()) for tc in range(T): M, N, K = map(int,input().split()) matrix = [ [0] * M for _ in range(N) ] visited = [ [False] * M for _ in range(N) ] cnt = 0 # input 값을 k 번 받아오며 그래프에 1 추가 for _ in range(K): A, B = map(int,input().split()) matrix[B][A] = 1 for i in range(N): for j in range(M): # matrix i, j 가 1이고 방문하지 않았을 경우 if matrix[i][j] == 1 and not visited[i][j]: # DFS 함수 호출 DFS((i,j)) # 끝나면 cnt 증가 cnt += 1 print(cnt)
4. 문제를 풀고난 후 생각
- 깊이 우선 탐색과 방향배열을 이용하여 조건에 맞을 경우 방문처리 및 함수 실행이 종료 후 cnt 값을 증가 시키는 방식으로 해결했다.
- 별도로 구현한 부분은 없고 stack 방식을 통해서 문제를 해결했다.
- 깊이 우선 탐색의 경우 어느정도 틀이 정해져 있어서 BOJ 1260 번을 안보고 작성하여 해결한 후 이러한 문제를 접하는 것이 좋은 것 같다.
5. 문제를 푸는데 도움이 되는 지식
- DFS(깊이 우선 탐색)
- 방향 배
'Python_알고리즘 > Silver II' 카테고리의 다른 글
2644. [Python]촌수계산 (0) 2023.09.04 5002. [Python]도어맨 (1) 2023.08.27 1564. [Python]팩토리얼5 (0) 2023.08.13 5397. [Python]키로거 (0) 2023.08.11 1260. [Python]DFS와 BFS (0) 2023.08.08