[코딩테스트] 기본반A 19일차

• 문제 이름: 유턴 싫어(https://www.acmicpc.net/problem/2823)
• 문제 유형: 그래프 이론
• 난이도: S2
• 언어: Python
• 문제 탐색하기
• 시간 복잡도
• 코드 설계하기
• 시도 회차 수정사항
• 정답 코드

import sys

from collections import deque

# 방향 (상, 하, 좌, 우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_dead_end(r, c, grid, R, C):
    """ r, c에서 4방향에 대해 모두 연결될 수 있는지 확인한다.
        3방향 이상이 막히면 막다른 길이다.
    """
    count = 0
    for dr, dc in directions:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '.':
            count += 1
    return count == 1  # 1방향만 열린 경우는 막다른 길이다.

def is_no_dead_end(R, C, grid):
    """ 마을의 지도를 보고 막다른 길이 있는지 확인 """
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '.':
                if is_dead_end(r, c, grid, R, C):
                    return True
    return False

# 입력 처리
R, C = map(int, sys.stdin.readline().rstrip().split())
grid = [list(sys.stdin.readline().rstrip()) for _ in range(R)]

# 마을에 막다른 길이 있으면 1, 없으면 0 출력
if is_no_dead_end(R, C, grid):
    print(1)
else:
    print(0)