백준 2667번 파이썬 풀이

홍태리·2022년 2월 14일
0

백준

목록 보기
6/9
post-thumbnail

첫 시도, 잘못된 코드

#백준 2667번

N = int(input())

house = []
for _ in range(N):
    house.append(list(map(int, input())))

visited = [[False for _ in range(N)] for _ in range(N)]

house_group = []

def find_house_group(x:int, y:int) -> int:
    count = 0
    if not (0 <= x <= N-1 and 0 <= y <= N-1):
        return count
    
    if visited[x][y]:
        return count
    elif not house[x][y]:
        visited[x][y] = True
        return count
    else:
        count += 1
        visited[x][y] = True
        count += find_house_group(x-1, y)
        count += find_house_group(x, y-1)
        count += find_house_group(x, y+1)
        count += find_house_group(x+1, y)
    return count

for x in range(N):
    for y in range(N):
        if visited[x][y]:
            continue
        elif not house[x][y]:
            visited[x][y] = True
            continue
        else:
            house_num = find_house_group(x, y)
            house_group.append(house_num)

house_group_num = len(house_group)
print(house_group_num)

if house_group_num > 0:
    for n in house_group:
        print(n)

아무리 생각해도 어디서 틀렸는지를 모르겠어서 고수분께 피드백을 요청드렸다...

어이없게도 '오름차순으로 정렬'하라는 문제의 마지막 요구사항을 빠뜨린 것.

그 외에도 여러모로 피드백을 해주셔서 많이 배울 수 있어 좋았지만, 허탈한 감정은 어쩔 수 없나보다.

수정된 코드

#백준 2667번

#재귀 함수 정의
def find_house_group(N:int, house:list, row:int, col:int, visited:list) -> int:
    count = 0
    #좌표가 지도를 이탈하는 경우 : 무시 // base case - 아무것도 하지 않고 넘어가는 경우
    if not (0 <= row <= N-1 and 0 <= col <= N-1):
        return count

    #방문한 적이 있을 때
    if visited[row][col]:
        return count
    
    #방문한 적은 없지만 아파트가 없을 때
    elif not house[row][col]:
        visited[row][col] = True
        return count
    
    #방문한 적이 없고 아파트가 있는 경우
    else:
        count += 1
        visited[row][col] = True
        count += find_house_group(N, house, row-1, col, visited)
        count += find_house_group(N, house, row, col-1, visited)
        count += find_house_group(N, house, row, col+1, visited)
        count += find_house_group(N, house, row+1, col, visited)
    return count

#지도 크기 입력
N = int(input())

#지도 행렬 입력
house = []
for _ in range(N):
    house.append(list(map(int, input())))

#방문 여부 리스트 정의
visited = [[False for _ in range(N)] for _ in range(N)]

#단지 크기 리스트 정의
house_group = []

#지도의 모든 영역에 대하여 재귀함수 실행
for i in range(N):
    for j in range(N):
        count = find_house_group(N, house, i, j, visited)
        if count:
            house_group.append(count)

#house_group 리스트 정렬, house_group 크기 저장
house_group.sort()
house_group_num = len(house_group)

#결과 출력
print(house_group_num)
if house_group_num:
    for n in house_group:
        print(n)
profile
스타트업을 준비하는 대학생입니다.

0개의 댓글