[Baekjoon] 1012. 유기농 배추

1012번: 유기농 배추

문제포인트

• 정점을 돌면서 dfs 실행횟수를 구한다.
• 재귀 제한을 풀어준다.

에러원인

• 델타탐색 돌때 새로운 변수를 사용하지 않고 i,j 를 써서 for문을 돌 때 기존의 i, j 가 갱신되어버렸다. 
• for문을 돌때마다 다시 원래 위치로 리셋되어야 하므로 새로운 변수를 사용해야 한다.

해결

• nx, ny로 새롭게 변수명을 지정해주었다.

# 이차원배열의 정점을 돌면서 dfs 실행한다. 방문했으면 건너뛴다. dfs 실행횟수만 계산하면된다. 재귀 제한 풀어주어야한다.
import sys
sys.setrecursionlimit(100000)

# 이하코드 사용시 변수 i, j 가 갱신되어 오류 발생
# def dfs(i, j):
#     visited[i][j] = 1
#     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상하좌우
#     for dx, dy in directions:
#         i, j = i + dx, j + dy
#         if i < 0 or i >= n or j < 0 or j >= m:  # 미해당시 다시 반복문 실행
#             continue
#         if board[i][j] == 1 and not visited[i][j]:
#             dfs(i, j)

def dfs(x, y):
    visited[x][y] = 1
    directions = [(-1, 0), (1, 0), (0, -1), (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 board[nx][ny] and not visited[nx][ny]:  # 배추가 있고 방문하지 않은 경우
            dfs(nx, ny)

for _ in range(int(input())):
    m, n, k = map(int, input().split())
    visited = [[0] * m for _ in range(n)]
    board = [[0] * m for _ in range(n)]    # 가로 m, 세로 n인 배추밭(n행 m열)
    for i in range(k):
        x, y = map(int, input().split())
        board[y][x] = 1     # 행렬과 x,y 좌표 반대이므로 주의!

    cnt = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] and not visited[i][j]:  # 배추가 있고 방문하지 않은 경우
                dfs(i, j)
                cnt += 1

    print(cnt)

기타 풀이 (처음 풀이)

좌표를 튜플로 만들어서 nodes 배열에 넣고

그 배열을 모두 돌면서 인접했는지 여부를 판단하여 노드끼리 연결한 뒤

만든 그래프로 dfs를 실행하는 알고리즘이다.

매우 노가다성이 짙었다...omg..

아래가 상단풀이, 위가 처음풀이. 메모리는 동일하나 연산 소요시간이 10배 차이가 난다. 비효율적인 코드이다.

통과했음에 자축을 잠깐 했지만.. 다음부터는 위 방법으로 풀자!! :)

import sys
sys.setrecursionlimit(100000)
t = int(input())

def dfs(idx, node):
    visited[idx] = 1
    for w in adj[idx]:
        link_idx = nodes.index(w)
        if not visited[link_idx]:
            dfs(link_idx, w)


for tc in range(t):
    m, n, k = map(int, input().split())
    visited = [0]*k
    nodes = []
    adj = [[] for _ in range(k)]

    for i in range(k):
        n1, n2 = map(int, input().split())
        node = (n1, n2)
        nodes.append(node)

    for j in range(k):
        for e in range(k):
            # x축이 같고 y축이 1차이
            if nodes[j][0] == nodes[e][0]:
                if abs(nodes[j][1] - nodes[e][1]) == 1:
                    adj[j].append(nodes[e])
                    # adj[e].append(nodes[j])

            # y축이 같고 x축이 1차이
            if nodes[j][1] == nodes[e][1]:
                if abs(nodes[j][0] - nodes[e][0]) == 1:
                    adj[j].append(nodes[e])
                    # adj[e].append(nodes[j])

    cnt = 0
    for idx, node in enumerate(nodes):
        if not visited[idx]:
            dfs(idx, node)
            cnt += 1

    print (cnt)