관리 메뉴

차근차근

[백준 1012] 유기농 배추 본문

대학교/Algorithm

[백준 1012] 유기농 배추

SWKo 2020. 9. 8. 23:05

0. 제목

  • 백준 1012 유기농 배추
  • BOJ 1012 유기농 배추
  • 파이썬 1012 유기농 배추
  • Python 1012 유기농 배추

1. 문제

www.acmicpc.net/problem/1012

 

1012번: 유기농 배추

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 �

www.acmicpc.net


2. 풀이

  • 2차원 배열 형태의 문제에서 좌표 입력을 받을 때 (x, y)를 arr[y][x] 로 표현하는 것을 항상 생각하며 푼다.
  • 파이썬에서 setrecursionlimit으로 재귀 허용 깊이를 늘려주지 않으면 런타임 오류가 뜨는 경우가 있어, 재귀 허용 깊이를 수동으로 늘려주는 코드를 상단에 적어주어야 한다.
  • dfs함수를 선언할 때 좌표의 각 점을 인자로 받는다. 이 문제에서는 상, 하, 좌, 우 만으로 움직일 수 있기 때문에 directions라는 배열에 이동 가능 거리 좌표를 넣고, 다음 좌표(next X, next Y)를 구한다. 
  • next X, next Y가 0보다 작거나 주어진 범위를 넘어가면 continue로 해당 차시 반복을 넘어가고 그것이 아니라면 방문해야하는 점이지만 아직 방문하지 않은 점에 대하여 재귀적으로 dfs함수를 실행한다.
  • 테스트 케이스마다 개수(result)를 출력해주면 된다.

3. 코드

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
import sys
sys.setrecursionlimit(100000)
 
def dfs(x, y):
    visited[x][y] = True
    directions = [(-10), (01), (10), (0-1)]
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)
    
for _ in range(int(input())):
    m, n, k = map(int, input().split())
    array = [[0* m for _ in range(n)]
    visited = [[False* m for _ in range(n)]
    for _ in range(k):
        y, x = map(int, input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i, j)
                result += 1
                
    print(result)
 

 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 1904] 01타일  (0) 2020.09.10
[백준 1325] 효율적인 해킹  (0) 2020.09.09
[백준 2606] 바이러스  (0) 2020.09.08
[백준 1697] 숨바꼭질  (0) 2020.09.06
[백준 1260] DFS와 BFS  (0) 2020.09.05
0 Comments
댓글쓰기 폼