[백준/Python] #2823 유턴싫어

문제

알고리즘

문제에 "이 마을에 막다른 길이 없다면, 상근이는 임의의 한 길에서 시작해서, 갈 수 있는 어떤 방향으로 움직이더라도, 유턴을 하지 않고 그 위치로 돌아올 수 있어야 한다." 라는 조건이 존재하므로, 어떤 길에서 이동할 수 있는 길이 1이하 칸이 존재한다면 해당 마을에는 막다른 길이 존재하게 된다.

그러므로 모든칸을 조사하면서 상,하,좌,우로 움직일 수 있는 칸의 개수를 카운팅하면서 1이하인 칸이 존재한다면 해당 마을은 막다른 길이 된다.

코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())
arr = [input().strip() for _ in range(r)]

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

flag = False
for i in range(r):
    for j in range(c):
        if arr[i][j] == '.':
            count = 0
            
            # 갈수있는 길의 개수 확인
            for k in range(4):
                nr, nc = i + dx[k], j + dy[k]

                if 0 <= nr < r and 0 <= nc < c:
                    if arr[nr][nc] == '.':
                        count += 1

            if count < 2:
                flag = True
                break

    if flag:
        break

if flag:
    print(1)
else:
    print(0)