[BOJ] 2615(S1): 오목 & 16719(G5): ZOAC

해당 문제를 확인하시고 싶으면 아래 링크를 통해 확인해주세요!
https://www.acmicpc.net/problem/2615
https://www.acmicpc.net/problem/16719

2615: 오목 (S1)

생각하지 못한점

• 처음에는 8개 방향 모두 탐색해야겠다 생각함 (상하좌우 + 대각선4방향)
  - 근데 생각해보니까 굳이 그럴필요는 없겠더라구요..?
  - 위쪽에 있으면 어짜피 오목인지 확인도 못하기 때문에..

문제점

위의 로직을 생각못한것만 빼면 사실 로직은 생각하기 쉬웠던 것 같다. 오히려 생각할건 없고 그냥 문제에 나와있는대로만 작업하면 어렵지 않은 문제였을 거 같다.

근데 그냥 코드 자체를 잘 못짜고 있는 것 같다. 구현력이 아직 많이 부족한 것 같다.
계속해서 알고리즘 주기적으로 1-2문제 풀어보면 충분히 늘거라고 생각한다!
꾸준함이 최고!

배운점

• 이 문제에서는 exit 메서드를 사용해야 한다. exit 메서드도 사용할 수 있다는 것을 항상 생각할 것.
• 이건 몰랐는데.. 이전 코드에서 계속해서 런타임 에러가 발생했는데 그 이유가 while문의 조건문 때문이었음. 나는 처음에 baduk == omok[nx][ny] and 0 <= nx < 19 and 0 <= ny < 19 이렇게 작성했었는데 이부분이 문제였다.
• 내가 작성한것처럼 작성하면 nx와 ny를 0부터 19사이를 비교하기 전에 baduk과 동일한지 비교하기 때문에 IndexError가 발생할 수 있다. 따라서 저렇게 and나 or로 조건 연결해줄때도 순서 생각하자!

code

"""
백준 2615 (S1): 오목
https://www.acmicpc.net/problem/2615
"""

omok = [list(map(int, input().split())) for _ in range(19)]   # 19x19 오목판 입력받음

# 오른쪽, 아래, 오른쪽아래, 오른쪽위
dx = [0, 1, 1, -1]
dy = [1, 0, 1, 1]

for x in range(19):
  for y in range(19):
    if omok[x][y] != 0:   # 바둑알이 놓여져있는 상태
      baduk = omok[x][y]   # 해당 위치의 바둑돌 (흰색 / 검은색)
      for d in range(4):   # 4개 방향으로 탐색진행
        # 이동한 좌표
        nx = x + dx[d]
        ny = y + dy[d]
        count = 1   # 바둑돌 개수

        while 0 <= nx < 19 and 0 <= ny < 19 and baduk == omok[nx][ny]:
          count += 1
          
          # 오목이 완성되었을때 육목 확인 -> 앞쪽 또는 뒷쪽
          if count == 5:
            if (0 <= nx + dx[d] < 19 and 0 <= ny + dy[d] < 19 and omok[nx + dx[d]][ny + dy[d]] == baduk) or (0 <= x - dx[d] < 19 and 0 <= y - dy[d] < 19 and omok[x - dx[d]][y - dy[d]] == baduk):
              break
            else:
              print(baduk)
              print(x+1, y+1)
              exit(0)
          else:
            # 좌표 추가이동
            nx += dx[d]
            ny += dy[d]
        

print(0)

16719: ZOAC (G5)

문제에서 가장 중요한 부분은 이부분이다.
아직 보여주지 않은 문자 중 추가했을때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는것

로직 생각

• 문자열에서 사전 가장 앞쪽에 나올 단어를 선택함
• 선택한 부분 뒤쪽(오른쪽) 먼저 확인함
• 나눈 부분에서도 사전 가장 앞쪽에 나올 단어를 하나씩 선택함

ex) STARTLINK을 보여주고 싶다
- A
- AI
- AIK
- ALIK VS AINK => AINK
- ALINK
- ARLINK
- ARTLINK
- SARTLINK
- STARTLINK

생각하지 못한점 + 문제점

• 일단 이 로직을 생각하기에 좀 시간이 걸렸던 것 같다. 문제 이해력이 조금 부족..한듯..? ㅎㅎ
• 재귀함수를 사용할 수 있겠다고 생각하긴 했는데 아직 재귀함수 사용에 대해서 조금 두려움이 있어서 그냥 깡으로 구현하려고 했으나 하다가 너무 오래걸리고 산으로 가는거 같아서 포기..
• 결국 다른분의 풀이를 보고 재귀함수 감을 조금 잡고 혼자 코드를 작성해서 풀이완료
• merge 정렬처럼 왼쪽-오른쪽 부분을 나눠서 진행할 때 index 설정에 조금 애를 먹었다.

code

"""
백준 16719 (G5): ZOAC
https://www.acmicpc.net/problem/16719
"""

"""
아직 보여주지 않은 문자 중 추가했을때의 문자열이 사전 순으로 가장 앞에 오도록 하는 문자를 보여주는것?
ex) STARTLINK을 보여주고 싶다
- A
- AI
- AIK
- ALIK VS AINK => AINK
- ALINK
- ARLINK
- ARTLINK
- SARTLINK
- STARTLINK
"""


def check(arr, idx):
  if len(arr) == 0:
    return

  minLetter = min(arr)  # 사전의 가장 앞쪽 단어
  minLetterIdx = arr.index(minLetter)  # 가장 앞쪽 단어 idx
  result[minLetterIdx + idx] = minLetter
  print("".join(result))  # 결과확인 변수 출력

  # 오른쪽
  check(arr[(minLetterIdx + 1):], idx + minLetterIdx + 1)
  # 왼쪽
  check(arr[:minLetterIdx], idx)


word = input()  # 문자열 입력
result = [''] * len(word)  # 결과확인 변수
check(word, 0)

배운점

재귀함수를 사용하면 이렇게 간단해지는걸...
재귀함수 문제를 조금 많이 풀어서 감을 잡아야할 것 같다..!