[Python Algorithm] 유기농 배추 BOJ #1012

문제

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

내 문제 풀이

t = int(input())
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
queue = []

for _ in range(t):
    m, n, k = map(int, input().split())  # 가로길이, 세로길이, 배추 개수
    space = [[0] * m for _ in range(n)]  # 배추밭
    count = 0

    for _ in range(k):
        y, x = map(int, input().split())
        space[x][y] = 1

    def bfs():
        index = 0

        while len(queue) > index:
            x = queue[index][0]
            y = queue[index][1]
            index += 1

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

                if nx < 0 or ny < 0 or nx >= n or ny >= m or space[nx][ny] == 0: continue

                space[nx][ny] = 0
                queue.append((nx, ny))

    for i in range(n):
        for j in range(m):
            if space[i][j] == 1:
                queue.append((i, j))
                space[i][j] = 0
                count += 1
                bfs()
                queue = []

    print(count)

👉 bfs/dfs 문제인데, dfs로 풀면 더 쉬울 것 같지만 내가 bfs에 더 약한 것 같아서 bfs로 풀어봤다.

• 2중 for문으로 땅을 한 칸씩 탐색하면서 1이 나오면 bfs 함수를 돌려주었다.
• bfs 함수에서는 dx, dy 리스트를 활용하여 상하좌우를 탐색해주었다.
  1을 만난다면 queue에 해당 자리를 추가해서 탐색을 계속하도록 해주었고,
  1이 있던 자리는 0으로 바꿔주어 다시 같은 탐색을 하지 않도록 했다.

✔️ 이 문제에서 잘 체크해줘야 할 점은,

다른 dfs, bfs 문제와는 다르게 배추가 있는 자리를 m, n으로 표시해주었기 때문에
리스트에서 해당 자리를 체크해줄 때 x, y가 아니라 y, x로 바꿔서 배추의 자리를 넣어줘야 한다.

 

(이전에 swift를 이용해서 dfs로 풀었던 게시글 -> https://seolhee2750.tistory.com/129)

 

💡 피드백

• 쉬운 문제라 금방 풀었는데, 이상하게 자꾸 오류가 나서 보니까
  파이썬은 논리 연산자를 || 말고 or 라고 써야되더라,,!
  파이썬을 오랜만에 쓰니까 또 헷갈린다.ㅎ 화이팅,,