14413. 격자판 칠하기

14413. 격자판 칠하기

문제

풀이(BFS)

1. 입력값 알맞게 변수에 저장하기
   문제에서 입력란을 보면 첫 번째 줄에 3, 두 번째 줄에 3, 6 세 번째줄 부터는 행렬이 나온다.
   맨 처음 3은 테스트케이스 수이고 3, 6은 row, col값이다. 그 밑에 행렬은 row, col값에 대한 행렬이다.
   이것을 변수화 하면 다음과 같다.
   
   n, m은 row, col값이고 row만큼 for문을 돌아 graph에 넣는다.

2. 행렬 값중에서 ?가 아닌 '#', '.'의 위치를 알아낸다. 그 이유는 정해진 '#' 또는 '.'위치에서 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")