study/문제 풀이

백준 - 유기농배추(1012)

올스왑 2022. 3. 6. 23:08

 

 

1012번: 유기농 배추

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

www.acmicpc.net

DFS/BFS 문제이다. dfs/bfs 문제는 오랜만에 풀어보는데도 이전에 쓴 포스팅 보면서 잠깐 복습해보니 금방 풀 수 있었다.

dfs/bfs 문제에 대한 풀이 방식을 간단히 적어놓았다. 풀어본 적이 별로 없다면 한 번 보고 오면 금방 이해가 될 것이다.(https://jang-sn.tistory.com/89?category=943527)

 

문제: 배추 밭에 해충이 있는데 해충을 잡으려면 배추흰지렁이를 풀어야 한다. 이 지렁이는 인접한 배추로 이동이 가능하다. 문제에는 배추밭의 크기와 배추가 심긴 위치를 알려준다. 그러면 배추밭의 해충을 잡기 위해 필요한 배추흰지렁이가 최소 몇 마리가 필요한지 출력하면 된다.

 

우선 주어진 배추 위치들을 배열에 담는다.

1) 배열에서 배추 위치 하나를 꺼낸다. 그리고 그 배추 위치를 visit이라는 배열을 만들어 삽입한다.

2) 꺼낸 배추 위치에 인접한 곳에 배추가 있는 지 확인한다.

3) 인접한 곳에 배추가 있다면, 처음 주어진 배추 위치 배열에서 그 원소를 제거하고, 그 배추의 위치를 visit 마지막 위치에 삽입한 후 다시 2)로 가서 인접한 곳에 배추가 있는지 확인한다.

4) 인접한 곳에 배추가 없다면, visit에서 해당 배추 위치를 뺀다. 그리고 visit에 아무 원소도 없다면 필요한 배추흰지렁이 숫자에 1을 추가한다.

5) 아직 배추 위치 배열에 원소가 남아있다면 1)로 돌아가고 없다면 지금까지 필요한 배추흰지렁이 숫자를 반환한다.

 

pypy3로 제출해서 정답.

import sys

k = int(sys.stdin.readline().rstrip())
answer = []
for _ in range(k):
    amount = int(sys.stdin.readline().rstrip().split()[2])
    position = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(amount)]
    visited = [position.pop()]
    req_amount = 0
    while True:
        p = visited[-1]
        if [p[0] + 1, p[1]] in position:
            visited.append([p[0] + 1, p[1]])
            position.remove([p[0] + 1, p[1]])
            continue
        elif [p[0] - 1, p[1]] in position:
            visited.append([p[0] - 1, p[1]])
            position.remove([p[0] - 1, p[1]])
            continue
        elif [p[0], p[1] + 1] in position:
            visited.append([p[0], p[1] + 1])
            position.remove([p[0], p[1] + 1])
            continue
        elif [p[0], p[1] - 1] in position:
            visited.append([p[0], p[1] - 1])
            position.remove([p[0], p[1] - 1])
            continue
        else:
            visited.pop()
            if len(visited) == 0:
                req_amount = req_amount + 1
                if len(position) == 0:
                    answer.append(req_amount)
                    break;
                else:
                    visited.append(position.pop())

for i in answer:
    print(i)

배추흰지렁이