문제
내 풀이
- 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분 정리 /
반응형
'algorithm > BOJ' 카테고리의 다른 글
[백준 1202번] 보석도둑 c++ 풀이 (1) | 2023.12.07 |
---|---|
[백준 2042번] 구간 합 구하기 c++ 풀이 (0) | 2023.10.30 |
시간복잡도, 공간복잡도를 생각하면서 문제를 풀자. (1) | 2023.10.29 |
[백준 2143번] 두 배열의 합 C++ 풀이 (1) | 2023.10.28 |
[백준 1062번] 가르침 C++ 풀이 (0) | 2023.09.14 |