[백준] 1012. 유기농 양배추

문제

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

 

코드

from collections import deque

T = int(input())

for _ in range(T):
    n, m, k = map(int, input().split())     # 가로, 세로, 배추개수
    field = [[0 for _ in range(n)] for _ in range(m)]
    visit = [[False for _ in range(n)] for _ in range(m)]
    answer = 0

    # 배추 지도 그리기
    for l in range(k):
        x, y = map(int, input().split())
        field[y][x] = 1

    for i in range(m):  	# 세로
        for j in range(n):  # 가로
            if field[i][j] == 1 and not visit[i][j]:
                answer += 1

                # BFS 시작
                q = deque()
                q.append([j, i])
                visit[i][j] = True

                while q:
                    ex, ey = q.popleft()

                    # 4방향 탐색
                    for dx, dy in ([0, 1], [1, 0], [-1, 0], [0, -1]):   # 하, 우, 좌, 상
                        nx = ex + dx
                        ny = ey + dy

                        if 0 <= nx < n and 0 <= ny < m:  	# 범위내 이고
                            if field[ny][nx] == 1:  		# 배추가 심어져있고
                                if not visit[ny][nx]:   	# 방문한적 없으면
                                    q.append([nx, ny])
                                    visit[ny][nx] = True

    print(answer)

 

풀이

n, m, k = map(int, input().split())     # 가로, 세로, 배추개수
field = [[0 for _ in range(n)] for _ in range(m)]
visit = [[False for _ in range(n)] for _ in range(m)]
answer = 0

# 배추 지도 그리기
for l in range(k):
    x, y = map(int, input().split())
    field[y][x] = 1

filed는 배추밭이다.

배추를 하나도 심지 않은 상태로 초기화 하기위해 모두 0으로 채워진 배열을 만든다.

 

visit는 해당 좌표를 방문했는지 안했는지 알아보는 좌표다.

아직 아무곳도 방문하지 않았기 때문에 모두 False로 채워진 배열을 만든다.

 

answer은 정답이 될 지렁이의 개수다.

 

배추의 개수만큼 x와 y의 좌표를 받아서 filed 배열에 배추 심을곳의 좌표를 1로 바꿔준다. 

따라서 filed 배열에 0은 배추를 심지 않은곳이고, 1은 배추를 심은곳이 된다.

 

for i in range(m):  	# 세로
    for j in range(n):  # 가로
        if field[i][j] == 1 and not visit[i][j]:
            answer += 1

filed의 모든 좌표를 순서대로 돌면서

만약 배추가 심어져 있는 곳이고 아직 방문한적 없는 곳이라면

지렁이를 하나 풀어 answer에 1을 더한다.

그리고 후에 BFS 알고리즘을 이용해서 인접해 있는 배추들은 모두 방문처리 해줄것이다.

 

# BFS 시작
q = deque()
q.append([j, i])
visit[i][j] = True

먼저 큐를 하나 생성한다.

큐에 지금 방문한곳의 좌표를 넣고

visit 배열에 지금 방문한곳의 좌표는 True로 바꿔서 방문했다고 표기해준다.

 

while q:
    ex, ey = q.popleft()

    # 4방향 탐색
    for dx, dy in ([0, 1], [1, 0], [-1, 0], [0, -1]):   # 하, 우, 좌, 상
        nx = ex + dx
        ny = ey + dy

        if 0 <= nx < n and 0 <= ny < m:  	# 범위내 이고
            if field[ny][nx] == 1:  		# 배추가 심어져있고
                if not visit[ny][nx]:   	# 방문한적 없으면
                    q.append([nx, ny])
                    visit[ny][nx] = True

큐가 비어있는 상태가 될때까지 다음의 작업을 계속 반복한다. (방문할 인접한 배추가 더이상 없을때 큐가 비게 될것이다)

큐의 맨 왼쪽 요소를 꺼내서 각각을 ex, ey 변수에 넣어준다. 

ex는 현재 x좌표이고 ey는 현재 y좌표를 의미한다.

 

반복문을 이용하여 현재 좌표를 기준으로 4방향 탐색을 진행한다. dx는 x좌표 변화량, dy는 y좌표 변화량을 의미한다. 네 방향 각각에 대해 다음의 작업을 수행한다.

nx는 사방향 탐색으로 탐색될 다음 x좌표라는 의미다. nx변수에 현재 x좌표에 x좌표 변화량 만큼을 더해준다. 

ny는 사방향 탐색으로 탐색될 다음 y좌표라는 의미다. ny변수에 현재 y좌표에 y좌표 변화량 만큼을 더해준다.

 

만약 nx와 ny가 filed내의 범위이고

nx, ny 좌표에 배추가 심어져 있고

nx, ny 좌표에 방문한적이 없으면

큐에 nx, ny를 넣어주고

nx, ny좌표는 방문처리 한다.