[삼성sw 파이썬] 14413 격자판 칠하기

[삼성sw 파이썬] 14413 격자판 칠하기

 

문제

N x M 크기의 직사각형 격자판에서 각 칸의 크기는 1x1 크기의 정사각형 모양이다.

이 격자판을 흰색 또는 검정색으로 칠할 계획이다.

N  x M 크기의 행렬 A가 있어서, Ai,j 가 ‘#’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해야 하고, Ai,j 가 ‘.’라면 격자판의 i행 j열에 있는 칸은 흰색으로 칠해야 하며, Ai,j 가 ‘?’라면 격자판의 i행 j열에 있는 칸은 검은색으로 칠해도 되고 흰색으로 칠해도 된다.

이대 인접한 두 칸의 색은 항상 다르게 할 수 있는지 판단하는 프로그램을 작성해야한다.

 

입력

첫 번째 줄에는 테스트 케이스 수가 주어진다.

각 테스트 케이스 첫번째 줄에는 N,M이 주어지고 그다음줄에는 행렬 A가 N개의 줄에 나타난다.

 

출력

각 테스트 케이스마다 ?에 해당하는 칸의 새글 잘 정하여 인접한 두 칸의 색이 항성 서로 다르게 할 수 있다면 possible 그렇지 않다면 impossible 을 출력한다

 

풀이

BFS를 이용하여 문제를 풀었다.

'.' 이나 '#'의 X,Y좌표 찾아서 그 좌표 기준으로 전체를 탐색하는 방식으로 하였다.

하나의 점에서 인접한 면은 총 4개이기때문에 4방향으로 이동할수 있도록 해주고, 현재위치에서 인접한 면의 값이 ?일경우와 아닐 경우를 나누어서 풀었다.

이때 인접한 면의 값이 ? 인 경우에는 현재 값에따라 인접한 면의 값을 경정하고 q에 인접한 면의 값을 넣어서 다시 탐색하도록 한다.

인접한 면의 값이 ? 가 아닌경우는 이미 색이 결정된 위치이기에 그 주변 인접한 것들과 비교하여 서로 같은게 있는지를 판별한다 .

만약 서로 색이 같다면 bfs를 탈출하도록 하여 impossible를 출력하도록 하였다.

코드

from collections import deque

t=int(input())

for test in range(1,t+1):
    ans="possible"
    n,m=map(int,input().split())

    array=[list(input()) for _ in range(n)]
    v=[[False for _ in range(m)] for _ in range(n)]

    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    
    q=deque()
    for i in range(n):
        for j in range(m):
            if array[i][j]!='?':
                q.append((i,j))
                v[i][j]=True
                break


    while q:
        x,y=q.popleft()
        
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if not v[nx][ny]:
                    if array[nx][ny]=="?":
                        if array[x][y]=="#":
                            array[nx][ny]="."
                            v[nx][ny]=True
                            q.append((nx,ny))
                        elif array[x][y]==".":
                            array[nx][ny]="#"
                            v[nx][ny]=True
                            q.append((nx,ny))
                    elif array[nx][ny]==array[x][y]:
     
                        ans="impossible"
                        break
                    else:
                        v[nx][ny]=True
                        q.append((nx,ny))

        if ans=="impossible":
            break

    print(f"#{test} {ans}")