[baekjoon] 백준 2823번(파이썬): 유턴 싫어

문제

2823번: 유턴 싫어

알고리즘

- bfs 탐색을 통해 문제를 수행한다.

- 길의 좌표를 확인 후 하나의 길 좌표를 탐색한다.

- 모든 길은 연결되어있기 때문에 하나의 길만을 탐색하여 연결된 길을 탐색하면 된다.

- 4가지 방향에 길의 수를 체크하여 길의 개수가 2 미만일 경우 1을 리턴 받는다.

- 모든 길을 탐색하면 0을 리턴 받는다.

코드

import sys
from collections import deque


def bfs(v):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    q = deque([v])

    while q:
        a, b = q.popleft()

        # 각 정점에 길의 개수
        cnt = 0

        # 상/하/좌/우 탐색
        for i in range(4):

            x = a + dx[i]
            y = b + dy[i]

            # 범위 내에 있고 길이라면
            if -1 < x < r and -1 < y < c and graph[x][y] == ".":

                # 4가지 방향에 길의 수 체크
                cnt += 1

                # 탐색하지 않았다면 탐색
                if visited[x][y] == False:
                    visited[x][y] = True

                    q.append([x, y])

        # 4가지 방향을 탐색했을 때 길이 2가지 미만이면 1을 리턴
        if cnt < 2:
            return 1

    # 모든 구역을 탐색했으면 0을 리턴
    return 0


r, c = map(int, sys.stdin.readline().split())
chek = [] # 길 좌표 확인

# 그래프를 표현
graph = []
for i in range(r):
    graph.append(list(map(str, sys.stdin.readline().strip())))
    for j in range(c):
        if graph[i][j] == ".":
            chek.append([i, j])

visited = [[False] * c for _ in range(r)]

# 모든 길이 연결되어 있음으로 하나의 길만을 탐색
print(bfs(chek[0]))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법