스파르탄 365 3주차 (3) 유기농 배추

3주차

백준 1012번 단지번호붙이기

문제링크 : https://www.acmicpc.net/problem/1012

💡 풀이 전 계획과 생각

• 상하좌우 좌표를 이용하는 문제니 저번에 풀었던 섬의 개수 문제를 응용하여 풀자
  -> BFS를 이용하려 했으나 실패.. ㅠ (실패 원인을 아직 파악하지 못함)

💡 풀이

import sys
input = sys.stdin.readline

test_case = int(input())

def dfs(x, y):
    visited[x][y] = True
    dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if nx<0 or nx>=n or ny <0 or ny>=m:
            continue
        if plot[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)

for _ in range(test_case):
    m, n, k = map(int, input().split())
    plot = [[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]

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

    cnt = 0
    for i in range(n):
        for j in range(m):
            if plot[i][j] and not visited[i][j]:
                dfs(i, j)
                cnt += 1

    print(cnt)

🧐 막혔던 점과 고민

• 대체 어느 부분에서 오류인지 아직 찾지 못했다.
• visited를 최대한 이용하는 부분으로 코드를 짜고 싶었다.

👏🏻 알게된 개념과 소감

• 상하좌우, 총 4번을 반복해서 좌표 변경 (다른 방법)

def dfs(x, y):
    visited[x][y] = True
    dirs = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    for dx, dy in dirs:
        nx, ny = x + dx, y + dy
        if nx<0 or nx>=n or ny <0 or ny>=m:
            continue
        if plot[nx][ny] and not visited[nx][ny]:
            dfs(nx, ny)

• 계속 쓰이는 입력 방법

 m, n, k = map(int, input().split())
    plot = [[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]

• ??? 왜 .. 왜.. y가 먼저지.. 왜...
• 이해는 잘 가지 않지만 디버깅해보니 이렇게 해야 사람이 원하는 데로 컴퓨터가 받아들임을 알 수 있었다. y, x가 아닌 x, y 순으로 받으면 범위 초과 오류도 나왔다.
• 우선은 암기로 받아들이고 멘토님께 여쭤야 겠다.

  for _ in range(k):
        # velog: 우선은 외우자.. 
        y, x = map(int, input().split())
        plot[x][y] = 1