SWE(5110)_어디에_단어가_들어갈_수_있을까

작성일 | In

SWE 1979

  • N*N 크기의 단어 퍼즐을 만들려고 한다.

  • 주어진 퍼즐 모양에서 특정 길이 k를 갖는 단어가 들어갈 수 있는 자리의 수를 출력하는 프로그램 작성

  • 제약사항 N은 5이상 15이하 정수
  • K는 2이상 N이하의 정수
  • 첫 줄 총 테스트 케이스 개수
  • 이후 첫 번째 줄에는 단어 퍼즐의 가로, 세로 길이 N, 단어의 길이 K가 주어짐

  • 퍼즐의 각 셀 중, 흰색 부분은 1, 검은색 부분은 0으로 주어진다.

  • DFS, BFS를 돌릴 것도 없이, for문을 통해 확인한다.
  • 1을 만나면 값을 더해간다 -> 0을 만나면 check를 0으로 이를 다 한 뒤 그 값을 temp 배열에 저장

  • 그 뒤, 단어의 길이와 일치하는 것의 개수를 찾는다.

  • 3문제를 틀려서 확인해보니
  • max로 if문을 걸어버리면[3,4]가 등장했을 때, 찾지 못해버린다.
  • 단순히 temp 배열에서, 3이 나왔을 때, 그 오른쪽이 0이거나, 3이 배열의 마지막에 나왔을 때.

코드

TC = int(input())

for tc in range(1, TC+1):
    N, K = map(int, input().split())
    arr = []
    for i in range(N):
        arr.append(list(map(int, input().split())))

    # 가로 길이 찾기
    result = 0
    for i in range(N):
        temp = []
        check = 0
        for j in range(N):
            if arr[i][j] == 1:
                check += 1
            else:
                check = 0
            temp.append(check)
        if temp[-1] == K:  # 가장 마지막에 있는 경우
            result += 1
        for k in range(N-1):  # 마지막 제외 오른쪽에 0인 경우
            if temp[k] == K and temp[k+1] == 0:
                result += 1
        # print("#%s" % i, temp, result)
    # 세로 길이 찾기
    for j in range(N):
        temp = []
        check = 0
        for i in range(N):
            if arr[i][j] == 1:
                check += 1
            else:
                check = 0
            temp.append(check)
        if temp[-1] == K:  # 가장 마지막에 있는 경우
            result += 1
        for k in range(N-1):  # 마지막 제외 오른쪽에 0인 경우
            if temp[k] == K and temp[k+1] == 0:
                result += 1
        # print("#%s" % i, temp, result)
    print("#%d %d" % (tc,  result))

# arr = [[1, 1, 0, 1, 0, 1, 1, 1],
#        [0, 1, 0, 1, 0, 0, 0, 1],
#        [1, 1, 1, 0, 0, 1, 0, 1],
#        [0, 1, 0, 1, 0, 1, 1, 1],
#        [0, 0, 0, 1, 0, 1, 0, 1],
#        [1, 1, 1, 1, 1, 1, 0, 0],
#        [0, 1, 0, 0, 0, 1, 0, 1],
#        [1, 1, 1, 0, 1, 1, 1, 1]]
# N = 8
# K = 3

다른 사람 풀이

T = int(input())
for test_case in range(T):
    N, K = map(int, input().split())
    # 문자열로 행과 열을 입력 받는다.
    data_row = [''.join(input().split()) for _ in range(N)]
    data_col = [''.join(i) for i in zip(*data_row)]
    total = data_row.copy()
    total.extend(data_col)
    ans = 0
    for i in total:
        result = i.split('0')
        if '1' * K in result:
            ans += result.count('1' * K)
    print("#{} {}".format(test_case + 1, ans))
  • 이렇게도 풀 수 있단 걸 배웠다.

참고자료 [SWexperacademy]https://swexpertacademy.com

0%