99클럽 코테 스터디 _ 14일차 TIL (브루트포스)

 

< 문제 >

[백준] 2615. 오목 / 실버1

---

< 풀이 >

코드 변수 정의

• function : check
  • cnt : 연속된 같은 바둑알의 개수
  • ax, ay : 가장 왼쪽에 위치한 바둑알의 좌표
• function : f
  • directions : 탐색할 4가지 방향
  • is_valid : 5개의 같은 바둑알이 연속되어 있는지 확인
  • x, y : 5개의 같은 바둑알이 연속되어 있는 경우, 해당 바둑알 중 가장 왼쪽에 있는 위치

---

Brute Force
시간복잡도 : O(6000)    * 최대

# 5개의 같은 바둑돌이 연속되는지 확인하는 함수
def check(board, i, j, d1, d2):
    cnt, ax, ay = 1, i, j # 현재 돌 포함, 초기 위치 저장
	
    # 주어진 방향 (d1, d2)으로 이동하면서 같은 돌인지 확인
    for dx, dy in [(d1, d2), (-d1, -d2)]: # 한쪽 방향과 반대 방향 모두 검사
        nx, ny = i + dx, j + dy
        while 0 <= nx < 19 and 0 <= ny < 19 and board[nx][ny] == board[i][j]:
            cnt += 1
            if dx == d1 and dy == d2: # 처음 탐색 방향일 때만 ax, ay 업데이트
                ax, ay = nx, ny
            nx, ny = nx + dx, ny + dy
	
    # 5개의 돌이 정확히 연속되었는지 확인 (6개 이상은 인정 X)
    return (cnt == 5, ax, ay) if cnt == 5 else (False, -1, -1)

def f():
    board = [list(map(int, input().split())) for _ in range(19)] # 오목판
    
    # 가능한 방향 설정 (\ 대각선, / 대각선, 가로, 세로)
    directions = [(-1, -1), (1, -1), (-1, 0), (0, -1)]

    for i in range(19):
        for j in range(19):
            if board[i][j] in [1, 2]: # 바둑알이 있는 위치에서만 확인
                for k in range(0, 4):
                    is_valid, x, y = check(board, i, j, *directions[k])
                    if is_valid: # 이긴 바둑돌이 있으면 종료
                        print(board[i][j])
                        print(x + 1, y + 1)
                        return
    print(0) # 무승부인 경우 0 출력

f()

---

 

 

 

풀이 방식

1. 탐색 시작
   • 모든 좌표 (i, j)를 탐색하면서, 해당 위치에 1(검은 바둑알) 또는 2(흰 바둑알)이 있는 경우만 확인한다.
2. 4가지 방향으로 바둑돌이 연속하는지 확인
   • 네 가지 방향으로 연속된 바둑돌이 있는지 확인한다.
     1. (-1, -1): ↖ (왼쪽 위 대각선)
     2. (1, -1): ↙ (오른쪽 위 대각선)
     3. (-1, 0): ↑ (세로)
     4. (0, -1): ← (가로)
   • * (0, 1)(오른쪽)은 (0, -1)(왼쪽)과 동일한 결과를 가져오므로 필요없다.
3. check 함수로 5개의 바둑돌이 연속하는지 확인
   1. check 함수로 현재 위치 (i, j)에서 특정 방향으로 5개의 같은 돌이 연속하는지 확인한다.
   2. 승리 조건을 만족하면 즉시 종료하고,
      • 승리한 바둑돌(1 또는 2)
      • 가장 왼쪽에 위치한 돌의 좌표를 출력 (세로인 경우 가장 위에 있는 돌)
4. check 함수 (연속된 바둑돌 개수 확인)
   1. cnt는 연속된 같은 바둑돌의 개수를 저장
   2. ax, ay는 가장 왼쪽에 위치한 돌의 좌표를 저장
   3. 주어진 방향 (d1, d2)로 이동하면서 같은 바둑돌이 있는지 확인한다.
   4. 반대 방향 (-d1, -d2)도 확인하며 총 개수(cnt)가 5인지 확인한다.
   5. 5개의 돌이 연속되었을 경우 True와 ax, ay를 반환한다.
   6. 6개 이상 연속되었거나 5개 미만이면 False를 반환한다.

---

< 회고 >

🤔 💭_

바둑알이 승리할 조건에 세로가 있을 수 있다는 것을 고려하지 않아서 틀렸었다.

 

처음에는 바둑알의 개수를 탐색할 때, 한 방향에 -1을 곱하여 반대 방향으로 만들어서 할 생각을 하지 못하고 directions에 반대방향 요소도 다 집어넣어 총 8개의 요소를 탐색하는 방식으로 했었다. 더 효율적인 방법을 찾기 위한 고민을 했었던 것 같다.

 

방향 설정은 대각선 2개, 가로, 세로로 잡았는데 가장 왼쪽에 위치하는 좌표를 찾기 위한 각각의 방향을 원방향으로 해서 원방향으로 탐색할 때만 ax, ay를 업데이트하는 방식으로 좌표를 구했다.