[Python] 백준 16956

16956번 - 풀이 1( bfs로 풀이)

#백준 16956 풀이 1

import sys
from collections import deque
input = sys.stdin.readline
r, c = map(int, input().split())
graph = [list(map(str, input().rstrip())) for _ in range(r)]
visited = [[False] * c for _ in range(r)]
d_row = [0, -1, 0, 1]
d_col = [1, 0, -1, 0]

def bfs():
    queue = deque()
    flag = False
    for i in range(r):
        for j in range(c):
            if graph[i][j] == 'W':
                queue.append([i, j])
                visited[i][j] = True

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + d_row[i]
            ny = y + d_col[i]
            if 0<= nx < r and 0<= ny < c:
                if graph[x][y] == 'W' and graph[nx][ny] == 'S':
                    flag = True
                if graph[x][y] == 'W' and not visited[nx][ny] and graph[nx][ny] == '.':
                    graph[nx][ny] = 'D'
                    visited[nx][ny] = True

    if flag:
        print(0)
        return
    else:
        print(1)
        for row in graph:
            print(''.join(row))
        return
bfs()

 

16956번 - 풀이2 (단순 반복문)

 

# 백준 16956 - 풀이 2

n, m = map(int, input().split())
graph = []
for i in range(n):
    graph.append(list(input().rstrip()))

d_row = [0, -1, 0, +1]
d_col = [+1, 0, -1, 0]

flag = False

for i in range(n):
    for j in range(m):
        if graph[i][j] == 'W':
            for x in range(4):
                next_row = i + d_row[x]
                next_col = j + d_col[x]
                if next_row < 0 or next_col < 0 or next_row > n - 1 or next_col > m - 1:
                    continue
                if graph[next_row][next_col] == 'S':
                    flag = True
                    break
                if graph[next_row][next_col] != '.':
                    continue
                graph[next_row][next_col] = 'D'

if flag:
    print(0)
else:
    print(1)
    for i in graph: ## 이 부분 중요!!!
        print(''.join(i))