인프런 커뮤니티 질문&답변

import sys
sys.setrecursionlimit(10**6)

n = int(input())
arr = []
for _ in range(n):
    temp = input()
    arr.append([int(num) for num in temp])

dxs, dys = (-1, 1, 0, 0), (0, 0, -1, 1)


def valid_coord(x, y):
    if 0 <= x < n and 0 <= y < n:
        return True
    else:
        return False


# 1인 부분을 전부 탐색한 후 다 탐색하면 True를 return하는 함수
def dfs(x, y):
    global cnt

    if arr[x][y] == 0:
        return False

    if arr[x][y] == 1:
        arr[x][y] = 0
        cnt += 1

        for dx, dy in zip(dxs, dys):
            nx = x + dx
            ny = y + dy
            if valid_coord(nx, ny):
                dfs(nx, ny)

        return True

    return False


cnt_arr = []
# arr[0][0] = 0 # 이 것이 문제
for i in range(n):
    for j in range(n):
        cnt = 0
        if dfs(i, j):
            cnt_arr.append(cnt)

print(len(cnt_arr))
cnt_arr.sort()
for elem in cnt_arr:
    print(elem)

 질문 1.

정답은 똑같이 나오는데 위의 문제와 똑같은 문제인

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

위의 문제는 위의 코드로 통과가 되지 않습니다..ㅠㅠ

계속 고민해봤지만 왜 그런지는 모르겠습니다 선생님

--> 해결 되었습니다. arr[0][0] = 0 # 이 것이 문제

2번 질문

또한, 아래 강사님 풀이의 DFS 함수는 return 조건이 없는데
이럴 경우, 어떻게 함수가 탈출을 하는지 이해가 안갑니다...
보통 재귀 문제에서는 return 조건을 통해서 탈출을 하던데

아래 문제에는 return이 없어서 혼동이 옵니다...

def DFS(x, y):
    global cnt
    cnt+=1
    board[x][y]=0
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
            DFS(xx, yy)

아래는 전체 코드 입니다.

import sys
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]

def DFS(x, y):
    global cnt
    cnt+=1
    board[x][y]=0
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
            DFS(xx, yy)

if __name__=="__main__":
    n=int(input())
    board=[list(map(int, input())) for _ in range(n)]
    res=[]
    for i in range(n):
        for j in range(n):
            if board[i][j]==1:
                cnt=0
                DFS(i, j)
                res.append(cnt)
    print(len(res))
    res.sort()
    for x in res:
        print(x)