[백준 16924번] 십자가 찾기 파이썬 완전탐색 풀이

문제

---

내 풀이

- 2차원 배열 array에 .은 0으로, *은 1로 저장

- 1로 된 위치를 담은 배열인 center에서 순회 시작

- 방향벡터를 사용해 십자가 쪽으로 돌기

- 이때 돌면서 십자가로 채울 수 있는 부분에 1씩 더해준다. -> 나중에 십자가로 다 채워졌는지 확인하기 위해

- 십자가 방향을 돌았으면 방향벡터 * 2, 즉 size를 증가해서 또 돈다.

- 이런식으로 반복

 

- 출력은 배열에 1이 없어야 십자가로 *를 다 순회한 것이기 때문에 1이 없을 때 pos결과를 출력, 아니면 -1 출력

 

---

내 코드

#입력
n,m=map(int,input().split())
  
array=[[0]*m for _ in range(n)]
for i in range(n):
  array[i]=list(input())

#자료구조 만들기
for i in range(n):
  for j in range(m):
    if array[i][j]=='.':
      array[i][j]=0
    elif array[i][j]=='*':
      array[i][j]=1

#예외 케이스 제거
if n==0 or n==1 or n==2:
  print(-1)

else:
  #출력 저장
  pos=[]
  
  #순회 시작 후보
  center=[]
  for i in range(n):
    for j in range(m):
      if array[i][j]==1:
        center.append([i,j])
        
  #순회 시작
  dx=[-1,1,0,0]
  dy=[0,0,-1,1]

  for i,j in center:
    size=0
    flag=0
    x,y=i,j

    #while문을 돌면서 사이즈 키우기
    while(True):
      if(flag==1):
        break
      size+=1
      #상하좌우 돌면서 저장해놓기
      for dir in range(4):
        nx=x+dx[dir]*size
        ny=y+dy[dir]*size
        if nx<0 or nx>=n or ny<0 or ny>=m:
          flag=1
          break
        elif array[nx][ny]==0:
          flag=1
          break
        elif dir==3:
          array[x][y]+=1
          array[x+size][y]+=1
          array[x-size][y]+=1
          array[x][y+size]+=1
          array[x][y-size]+=1
          pos.append([i+1,j+1,size])

#답안 출력
  flag2=1
  for i,j in center:
    if array[i][j]==1:
      print(-1)
      flag2=0
      break
  if(flag2):
    print(len(pos))
    for i in pos:
      for j in i:
        if j==i[2]:
          print(j)
        else:
          print(j,end=" ")

---

주의점

- 방향 벡터는 범위 체크가 중요하다 (indexError)

- 문제 잘 이해하기 -> 십자가로 모든 *표를 채워야 한다는 점

- 함수로 분리하면 클린 코드가 가능하다

- 십자가, 방향벡터, 2차원배열은 출제 빈도가 꽤 높음

- 40분 문제 풀이 / 20분 틀린 점 고치기 / 10분 정리 /