입력값 알맞게 변수에 저장하기
문제에서 입력란을 보면 첫 번째 줄에 3, 두 번째 줄에 3, 6 세 번째줄 부터는 행렬이 나온다.
맨 처음 3은 테스트케이스 수이고 3, 6은 row, col값이다. 그 밑에 행렬은 row, col값에 대한 행렬이다.
이것을 변수화 하면 다음과 같다.
n, m은 row, col값이고 row만큼 for문을 돌아 graph에 넣는다.
행렬 값중에서 ?가 아닌 '#', '.'의 위치를 알아낸다. 그 이유는 정해진 '#' 또는 '.'위치에서 BFS를 통해 되는지 안되는지 판별 할 것이기 때문이다.
즉 '?'이면 건너뛰고 '#' 또는 '.'의 처음 위치값을 deque에 저장한다.
3.BFS로 possible한지 impossible한지 판별하기
예를 들어서 처음 q에 넣었을 때 #을 넣었다면 BFS탐색에서는 상, 하, 좌, 우가 "." 또는 "?"여야 한다. 만약 "#"라면 이것은 impossible한다.
row, col값이 행렬 밖에 위치하면 continue 시켜준다. 그리고 목표값과 현재값이 다르다면 impossible한다.(목표값은 "#"이지만 graph값은 "."일 때)
그리고 해당 위치 방문처리하고 상,하,좌,우 위치 값과 목표값을 deque에 넣는다.
이렇게 하여 flg1이 False라면 possible하다.
from collections import deque
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
n, m = map(int, input().split())
graph = []
flg = True
q = deque()
for j in range(n):
row = list(input())
graph.append(row)
for row in range(n):
for col in range(m):
if graph[row][col] != '?':
flg = False
q.append((row, col, graph[row][col]))
break
if not flg:
break
if not q: ## 행렬 전체가 ?일 때 무조건 possible
print("#"+ str(test_case) + " " + "possible")
continue
else:
visited = [[False for i in range(m)] for j in range(n)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
flg1= False
while q:
cur_row, cur_col, cur_target = q.popleft()
if cur_row < 0 or cur_row >= n or cur_col < 0 or cur_col >= m or visited[cur_row][cur_col]:
continue
if (cur_target == "#" and graph[cur_row][cur_col] == ".") or (cur_target == "." and graph[cur_row][cur_col] == "#"):
print("#"+ str(test_case) + " " + "impossible")
flg1 = True
break
else:
graph[cur_row][cur_col] = cur_target
visited[cur_row][cur_col] = True
for arr in direction:
new_row, new_col = cur_row + arr[0], cur_col + arr[1]
if cur_target == "#":
q.append((new_row, new_col, "."))
elif cur_target == ".":
q.append((new_row, new_col, "#"))
if not flg1:
print("#"+ str(test_case) + " " + "possible")