📌 문제 탐색하기
- R X C 크기의 지도에 빌딩(X), 도로(.)이 표시되어 있다. 임의의 도로 한 점에서 시작했을 때, 유턴을 하지 않고 시작 지점으로 돌아올 수 있는지 판단하는 문제이다.
- 문제에서 말하는 유턴이란 (1, 1) 위치에서 (1, 2)로 이동한 후, 바로 다시 (1, 1)로 이동하는 것을 말한다.
- 즉 유턴을 하지 않고 원점으로 돌아가기 위해서는 현재 위치해 있는 도로와 연결된 다른 도로가 최소 2개 이상이어야 한다.
💡 알고리즘 선택
- 지도에 있는 임의의 도로에서 BFS를 활용하여 상하좌우에 다른 도로가 2개 이상인지 확인하면 될 것 같다.
- 모든 도로가 서로 연결되어 있으므로 어느 점에서 시작하든 상관이 없을 것이다.
def BFS(start):
queue = deque([start])
visited[start[0]][start[1]] = 1
while queue:
count = 0
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if r > nx >= 0 and c > ny >= 0 and map[nx][ny] == '.':
count += 1
if visited[nx][ny] == False:
visited[nx][ny] = True
queue.append((nx, ny))
if count < 2:
return 1
return 0- 다음과 같이 BFS 내부에서 네 방향을 탐색하고, 각각의 좌표가 유효한 범위이고 도로가 맞으면 count를 1 증가시킨다.
- 네 방향을 모두 탐색했을 때, count가 2보다 작다면 유턴 없이 원점으로 돌아갈 수 없다고 판단하여 1을 return하고 그렇지 않다면 계속 BFS를 탐색하게 했다.
📌 코드 설계하기
1. 문제의 input을 받아서 r, c, map을 구현한다.
2. r x c 크기만큼 visited 리스트를 생성하여 방문 유무를 관리한다.
3. 위에 기술했던 것 같이 BFS를 구현하고 임의의 도로부터 탐색을 시작하여 연결된 도로가 2개 이상인지 확인한다.
4. BFS에서 return된 값을 출력한다.
📌 시도 회차 수정 사항 (Optional)
1회차
실수로 BFS 함수 내부에서 count 갯수를 판단할 때, 조건문을 if count < 1로 해버려서 틀렸음.
-> 도로가 2개 이상이어야 유턴 없이 원점으로 돌아갈 수 있으므로 조건문을 if count < 2로 수정함.
📌 정답 코드
from collections import deque
r, c = map(int, input().split())
map = []
for i in range(r):
map.append(input())
visited = [[False] * c for _ in range(r)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def BFS(start):
queue = deque([start])
visited[start[0]][start[1]] = 1
while queue:
count = 0
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if r > nx >= 0 and c > ny >= 0 and map[nx][ny] == '.':
count += 1
if visited[nx][ny] == False:
visited[nx][ny] = True
queue.append((nx, ny))
if count < 2:
return 1
return 0
for i in range(r):
for j in range(c):
if map[i][j] == '.':
start = (i, j)
print(BFS(start))