[소프티어] Lv2. 장애물 인식 프로그램

2️⃣ 장애물 인식 프로그램

https://softeer.ai/practice/6282

💡 아이디어

• DFS로 1을 발견하고, 상하좌우로 탐색하여 1을 또 발견하면 계속해서 카운트를 해주고, 상하좌우로 발견이 안되면 관둔다
• 각각의 구간별로 카운트를 해줘야하는데 이때 배열을 따로만들어서 길이를 세어주고, 초기화해주는 방식으로 풀이했다. 첨엔 숫자로 두고 했는데 자꾸 에러가 나서 구글링의 도움을 받았다.

✍🏻 풀이

n = int(input())

block = []

for i in range(n):
  block.append(list(map(int, input())))
def dfs(x,y):
  if x < 0 or x >= n or y < 0 or y >= n:
    return False    
  if block[x][y] == 1:  
    cnt.append(1)
    block[x][y] = 0
    dfs(x+1,y)
    dfs(x-1,y)    
    dfs(x,y+1)
    dfs(x,y-1)
    return True
  return False

result = 0
cnt_list = []
cnt = []

for i in range(n):
  for j in range(n):
    if dfs(i,j) == True:
      result += 1
      cnt_list.append(len(cnt))
      cnt = [] #초기화 

print(result)
cnt_list.sort()
cnt.sort()
for i in cnt_list:
  print(i)

🎅🏻 느낀점

dfs 오랜만에 하니 .. 까먹는다 ..