스파르탄 365 3주차 (2) 단지번호붙이기

3주차

백준 2667번 단지번호붙이기

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

💡 풀이 전 계획과 생각

상하좌우 좌표를 이용하는 문제였었는 데 🤔
: 현 시점을 기준으로 동서남북을 탐방해서 1인 곳만 방문 후 경로 찾자

💡 풀이

# 좌표 문제는 dx, dy 리스트 선언하면 접근이 쉬움
import sys
input = sys.stdin.readline

def dfs(x, y, cnt):
    # 상하좌우 탐방을 위한 리스트 
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    danzi[x][y] = 0
    # 상하좌우 탐방
    for i in range(4):
        # 상화좌우 움직이면서 변하는 현 좌표 
        now_x, now_y = x+dx[i], y+dy[i]
        # 예외 처리
        if now_x<0 or now_y<0 or now_x>=N or now_y>=N or not danzi[now_x][now_y]:
            continue
        cnt = dfs(now_x, now_y, cnt+1)
    return cnt

N = int(input())
danzi = [list(map(int, list(input().strip()))) for _ in range(N)]
cnt = 0
ans = []

for i in range(N):
    for j in range(N):
        if danzi[i][j] == 1:
            ans.append(dfs(i, j, 1))
print(len(ans))
# !정렬을 for문 안에서도 할 수 있구나
for i in sorted(ans):
    print(i)

🧐 막혔던 점과 고민

• 상하좌우를 어떻게 탐방했더라?

👏🏻 알게된 개념과 소감

• 상하좌우, 총 4번을 반복해서 좌표 변경

for i in range(4):
        # 상화좌우 움직이면서 변하는 현 좌표 
        now_x, now_y = x+dx[i], y+dy[i]

• 입력받으면서 바로 그래프 설정

danzi = [list(map(int, list(input().strip()))) for _ in range(N)]

• 반복문에서 바로 정렬해버리기

for i in sorted(ans):
    print(i)

💡 개선 방향

• dfs 함수를 재귀함수 구현에서 스택을 사용한 부분으로 구현하고 싶다.