[알고리즘|파이썬] 백준 2823 유턴 싫어

문제 링크: https://www.acmicpc.net/problem/2823

 

📌 문제 탐색하기

시간 제한: 1초
메모리 제한: 128 MB

 

✏️ 구해야 하는 정답

마을에 막다른 길이 존재하는지 확인해야 한다.

• 막다른 길이 없다면 0 출력

• 막다른 길이 있으면 1 출력

 

막다른 길의 정의:

• 길(.)이지만 상하좌우 이동할 수 있는 길이 1개뿐인 경우

---

📌 풀이하기 

문제 이해 및 조건 정리

• 지도는 R × C 크기의 격자로 이루어짐

• . : 길(이동 가능)

• X : 빌딩(이동 불가능)

• 길(.)끼리는 서로 연결되어 있음

• 목표: 모든 길(.)이 최소한 2개 이상의 연결된 방향을 가져야 함

 

반대로, 막다른 길이라 유턴을 해야하는 경우 그림과 같이 막다른 길에 둘려쌓여 있는 경우이다.

 

어떻게 풀것인가 🤔

1. 입력 받기

• R × C 크기의 지도를 2차원 리스트로 저장

 

2. 모든 길(.)에 대해 상하좌우 이동 가능 경로 탐색

• 상, 하, 좌, 우 네 방향((-1,0), (1,0), (0,-1), (0,1))을 탐색

• 이동 가능한 길(.)이 1개뿐이면 막다른 길

 

3. 출력 조건 확인

• 막다른 길이 존재하면 1 출력

• 그렇지 않으면 0 출력

 

---

📌 코드 설계하기

1. R, C input 받기

2. 마을 지도 입력받기

3. 상하좌우로 움직이면서 길이 있는 경우 확인

  - 한 방향으로만 이동 가능하면 막다른 길 => 1 출력

  - 그렇지 않다면 => 0 출력

---

📌 정답 코드

def has_dead_end(R, C, village):
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    for r in range(R):
        for c in range(C):
            if village[r][c] == '.':
                path_count = 0
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < R and 0 <= nc < C and village[nr][nc] == '.':
                        path_count += 1
                if path_count == 1:
                    return 1
    return 0

R, C = map(int, input().split())
village = [input().strip() for _ in range(R)]

print(has_dead_end(R, C, village))