Han Juhui

하나 둘 씩 정리해봅시다✨

업데이트:


오늘의 문제는 🚀 백준_16924번: 십자가 찾기이다.

..주말을 즐기다가 오늘안에 해결하지 못했다. 껄껄

그리고 문제 자체가 어려운 것도 한몫 한다…😂




테스트케이스 이해하기

image

위의 그림 처럼 *로 만들어진 십자가를 주어진 Input에서 찾는 문제이다.

image

결과값은 input에서 총 3개의 십자가를 찾을 수 있다는 것이다!

  • (3,4)에 길이가 1인 십자가
  • (3,5)에 길이가 2인 십자가
  • (3,5)에 길이가 1인 십자가


위와 같이 십자가를 찾아내서 총 갯수와 좌표, 길이를 차례대로 프린트 해주면 된다.



1차 시도 : 실패

오늘 시도는 예외점이 많아서… 다른 방법을 찾아야할 것 같다.

  • 알고리즘
  1. 이중포문을 돌려서 각각의 값에 접근 (가장 자리 1을 제외)
  2. *일 경우, for을 이용해서 왼쪽, 오른쪽, 위에, 아래를 확인해서 다 *일 경우 result에 i,j,길이 추가
  3. 길이를 늘려서 다시 확인해서 맞을 경우, result에 추가.
  4. result의 길이가 0이면 -1을 아니면, 내용물을 프린트


  • 문제점
    • 백준에 나와있는 예제 3번의 경우를 처리하지 못함.
    • 십자가 중간에 구멍이 나있을 경우 처리 못함
    • 시간 복잡도가 높음
    • 총체적난국…!
    • 다른 방법을 생각해야하는데 다 돌아다니면서 체크하는거 밖에 안떠오른다 흑흑😂



  • 시도 코드

    #입력
n,m = map(int, input().split())
arr=[list(map(str,list(input()))) for _ in range(n)]
  
result=[]
max = max(n,m)
dx=[1,-1,0,0]
dy=[0,0,1,-1]
  
for i in range(1,n-1):
    for j in range(1,m-1):
        if arr[i][j] == "*":
            count = 1
            while count < max:
                circle = 0
                for k in range(4):
                    i += dx[k]*count #길이 늘어나는 것 체크
                    j += dy[k]*count
                    if -1 < i < n and -1 < j < m:
                        if arr[i][j] == "*":
                            circle += 1
                    i -= dx[k]*count
                    j -= dy[k]*count
  
                if circle == 4: #십자가가 될 경우만 넣어 줌
                    result.append([i+1, j+1, count])
                count += 1
  
if len(result) == 0:
    print(-1)
else:
    print(result)

2차 시도 : 성공

아무리 생각해도 다 확인해보는거 말고는 생각이나지 않는다.

그래서 그냥 그대로 하고, 빈어레이를 만들어서 똑같이 만든후 확인하는 방식으르 더했다!

그랬더니 성공!

  • 알고리즘
  1. 이중포문을 돌려서 각각의 값에 접근 (가장 자리 1을 제외)
  2. *일 경우, for을 이용해서 왼쪽, 오른쪽, 위에, 아래를 확인해서 다 *일 경우 result에 i,j,길이 추가
  3. 길이를 늘려서 다시 확인해서 맞을 경우, result에 추가. 안맞을 경우 break로 탈출
  4. result의 내용물 꺼내서 input과 똑같이 만들어서 check 어레이를 만듦.
  5. input과 check를 비교
  6. 같으면 결과값 출력, 아니면 -1출력.



정답 코드

n,m = map(int, input().split())
arr=[list(map(str,list(input()))) for _ in range(n)]
check=[["."]*m for _ in range(n)]
result=[]
max = max(n,m)
dx=[1,-1,0,0]
dy=[0,0,1,-1]


#십자가 찾기
for i in range(1,n-1):
    for j in range(1,m-1):
        if arr[i][j] == "*":
            count = 1
            while count < max:
                circle = 0
                for k in range(4):
                    i += dx[k]*count
                    j += dy[k]*count
                    if -1 < i < n and -1 < j < m:
                        if arr[i][j] == "*":
                            circle += 1
                    i -= dx[k]*count
                    j -= dy[k]*count

                if circle == 4:
                    result.append([i+1, j+1, count])
                else:
                    break
                count += 1



#결과값으로 check 어레이 만들기
for i in range(len(result)):
    x =result[i][0]-1
    y =result[i][1]-1
    count = result[i][2] +1
    check[x][y] = "*"
    for j in range(1, count):
        for k in range(4):
            x += dx[k] * j
            y += dy[k] * j
            check[x][y] = "*"
            x -= dx[k] * j
            y -= dy[k] * j


#두 어레이가 같은지 확인하기
printResult = True
for i in range(n):
    for j in range(m):
        if arr[i][j] != check[i][j]:
            printResult = False
            break



#결과 프린트 하기
if printResult:
    print(len(result))
    # 정렬은 선택
    result.sort(key=lambda x: (x[0], x[1],-x[2]))
    for i in range(len(result)):
        print(' '.join(map(str, result[i])))

else:
    print(-1)



🚀Reference: 백준_16924번 - 십자가 찾기


카테고리:

업데이트:

참고