백준 - 2667번(DFS,BFS 문제지만 완전탐색으로 품)

DFS BFS 문제지만 해당 방법으로 어떻게 접근하는지 감이 잘 안 잡혀서 떠오르는 방식으로 주먹구구식으로 풀어봤다.

사실 DFS 와 BFS도 재귀(Recursion)의 일종이다. 따라서 재귀 함수를 이용해서 십자가 모양으로 탐색하는 것으로 진행했다.

탐색한 애들은 모두 0으로 바꿔준다. 이를 반복해서 재귀가 끝나면 새로운 tmp배열을 만드는 것으로 단지 구분이 가능하다.

다만 여기서 문제점이 발생한다.

만약 이차원 리스트 안에서 arr[0,0]을 십자가 모양으로 탐색을 하게 되면 arr [-1,0]과 arr [0,-1]도 탐색을 하게 된다.

처음에는 try except를 이용하려 했지만 이는 바람직한 방법이 아니다.

따라서 단지 전체를 0으로 감싸줬다.

주어진 미로 예시는 아래와 같다.

0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

이를 0으로 감싸면 다음과 같다.

 

000000000

001101000
001101010
011101010
000001110
001000000
001111100
001110000

000000000

 

이렇게 하고 탐색 범위를 (1,n+1)로 하면 인덱스 에러가 발생하지 않게 된다.

 

전체 코드는 다음과 같다.

import sys

n = int(sys.stdin.readline())

arr = []
ans = []

def count(arr,i,j,tmp):
    arr[i][j] = '0'
    tmp.append(i)
    tmp.append(j)

    if arr[i + 1][j] == '1':
        if i + 1 >= 0 and j >= 0:
            count(arr, i + 1, j, tmp)

    if arr[i - 1][j] == '1':
        if i - 1 >= 0 and j >= 0:
            count(arr, i - 1, j, tmp)

    if arr[i][j + 1] == '1':
        if i >= 0 and j + 1 >= 0:
            count(arr, i, j + 1, tmp)

    if arr[i][j - 1] == '1':
        if i >= 0 and j - 1 >= 0:
            count(arr, i, j - 1, tmp)


arr.append(['0'] * (n+2))
for i in range(n):
    temp = ['0']
    x = list(input())
    for j in x:
        temp.append(j)
    temp.append('0')
    arr.append(temp)
arr.append(['0'] * (n+2))

tmp = []

for i in range(1,n+1):
    for j in range(1,n+1):
        if arr[i][j] == '1':
            count(arr,i,j,tmp)
            ans.append(tmp)
            tmp = []

t_ans = []

for i in range(len(ans)):
    t_ans.append((len(ans[i]))/2)

t_ans.sort()

print(len(t_ans))
for i in t_ans:
    print(int(i))

DFS BFS로 푸는 방법도 공부하고 연습해 봐야겠다.