📌 문제 : 백준 2615번
📌 문제 탐색하기
stones : 바둑알 위치 정보
19 * 19 로 주어지는 바둑알 상태 정보를 통해 누가 이겼는지, 승부가 났는지 여부를 출력하는 문제이다.
문제 풀이
⭐️ 오목 게임 방법
- 상태 의미 :
1→ 검은 바둑알,2→ 흰 바둑알,0→ 바둑알 없는 곳- 같은 색이 연속 다섯 알 놓이면 🏆⭕️, 여섯 알 이상은 🏆❌
- 연속적 = 가로, 세로, 대각선 방향 연달아 위치함
- 2가지 색이 동시에 이기거나, 1가지 색이 2곳에서 이기는 경우는 ❌
- 승부가 났을 경우, 이긴 바둑알의 가장 왼쪽에 있는 바둑알의 가로줄 번호와 세로줄 번호를 순서대로 출력
문제에서 의해 2곳에서 이기는 경우는 없다고 했으므로 바둑판 상태 정보를 처음부터 확인한다.
바둑알이 있는 경우에 아래와 같이 승패를 판단한다.
- 그 위치를 먼저 저장 → 승리라면 해당 인덱스에
+1한 값 반환 - BFS를 통해 같은 색 바둑알이 몇개가 연달아 있는지 세기 → 딱 5개면 6개 이상은 아닌지 확인
- 딱 5개 뿐이면 승
- 아니라면 다른 곳 이동
가능한 시간복잡도
전체 바둑판 확인 →
BFS 함수로 오목 확인 →
최종 시간복잡도
으로 최악의 경우에도 1초 내에 연산 가능하다.
알고리즘 선택
바둑판 전체를 BFS로 탐색하면서 오목 찾기
📌 코드 설계하기
- BFS 함수 구현
1-1. 바둑알 수 변수 정의
1-2. 왼쪽 좌표 저장
1-3. 4가지 방향 탐색
1-3-1. 같은 방향으로 이동
1-3-2. 이동 위치가 범위내, 같은 색이면 BFS 탐색 지속
1-3-2-1. 오목 여부 체크
1-3-2-2. 맞으면 왼쪽 좌표 반환 - 방향 정의
- 필요한 입력 받기
- 바둑알 위치 확인해 BFS 수행
- 결과 출력
📌 시도 회차 수정 사항
1회차
#### 수정 전
# 5개 뿐이면 색 출력
print(color)
answer_x, answer_y = x, y
return answer_x + 1, answer_y + 1
#### 수정 후
# 5개면 승리이므로 원하는 결과 출력
print(color)
return answer_x + 1, answer_y + 1
# 승리 아무도 못함
return -1, -1- 예제 입력1을 넣었을 때 자꾸 출력이 0만 나왔다.
- 알고보니 정답을 리턴하는 코드를 for문 내에 넣어서 탐색이 끝나기 전에 값을 반환해 제대로 된 값을 얻을 수 없었다.
- 오목이 확인돼 승리한 상태가 아니라면 좌표값이
-1, -1가 되도록 해서 승리 결정 여부를 확인했다.
2회차
# 바둑알 위치 확인
answer_x, answer_y = -1, -1
for i in range(19):
for j in range(19):
if stones[i][j] != 0:
answer_x, answer_y = bfs(i, j)- 이와 같이 bfs를 수행했는데 좌표가 제대로 출력되지 않았다.
- 승리한 후에도 계속 bfs를 수행하다보니 잘못된 값이
answer_x,answer_y에 들어가 원하는 값을 얻을 수 없었다. - 탐색 중간에 승리함을 확인하면 탐색을 종료하도록 조건을 추가했다.
📌 정답 코드
import sys
from collections import deque
input = sys.stdin.readline
# 4가지 방향 정의 : 가로, 세로, 대각선 아래, 대각선 위
directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]
def bfs(x, y):
# 색 저장
color = stones[x][y]
# 탐색
for direction in directions:
queue = deque([(x, y)])
count = 1
answer_x, answer_y = x, y
while queue:
cx, cy = queue.popleft()
nx, ny = cx + direction[0], cy + direction[1]
# 바둑판 범위 안에 있고 같은 색이면 탐색
if 0 <= nx < 19 and 0 <= ny < 19 and stones[nx][ny] == color:
count += 1
queue.append((nx, ny))
# 6개 이상인지 확인
if count == 5:
# 육목 체크
if 0 <= x - direction[0] < 19 and 0 <= y - direction[1] < 19 and stones[x - direction[0]][y - direction[1]] == color:
break
if 0 <= nx + direction[0] < 19 and 0 <= ny + direction[1] < 19 and stones[nx + direction[0]][ny + direction[1]] == color:
break
# 5개면 승리이므로 원하는 결과 출력
print(color)
return answer_x + 1, answer_y + 1
# 승리 아무도 못함
return -1, -1
# 바둑 상태 입력
stones = [list(map(int, input().split())) for _ in range(19)]
# 바둑알 위치 확인
answer_x, answer_y = -1, -1
for i in range(19):
for j in range(19):
if stones[i][j] != 0:
answer_x, answer_y = bfs(i, j)
if answer_x != -1 and answer_y != -1:
break
if answer_x != -1 and answer_y != -1:
break
# 결과 출력
if answer_x == -1 and answer_y == -1:
print(0)
else:
print(answer_x, answer_y)
- 결과
