https://leetcode.com/problems/keys-and-rooms/
문제 파악
0번에서 쭉 이어지는 방이 있고 방에는 키가 있다. 이러한 키를 통해 다른 방을 출입할 수 있다.
접근 방법
문제에서 구하고자 하는 값은 모든 방의 방문 가능 여부이다. 각 방에는 다른 방으로 갈 수 있는 열쇠가 존재하며 이를 통해 아직 방문하지 못한 방으로 갈 수 있는 열쇠를 얻어 다음 방으로 이동해야 한다.
우선 첫 번째 방법으로 한 방에 이동할 때 마다 해당 방에서 얻은 모든 열쇠들을 통해 해당 방들을 방문하고 각 방에 있는 열쇠들을 얻는 과정을 반복할 수 있다(BFS).
다음 방법으로 한 방에 이동할 때 마다 해당 방에서 얻은 열쇠들 중 우선 하나의 열쇠를 통해 다음 방으로 이동하고 다음 방에서도 동일한 과정을 통해 더 나아갈 수 없을 때까지 진행하고 돌아올 수 있다(DFS).
방을 방문하고 탐색하기 위해 BFS를 사용했다. 먼저 시작점을 queue에 등록 후 방문 목록에 이에 해당하는 인덱스를 찾아서 사용하고 visited에 없는 것들을 순차적으로 추가하고 이렇게 문제를 접근해보자!
코드 구현
from collections import deque
from typing import List
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
# 방문 리스트 초기화
visited = [False] * len(rooms)
# BFS 정의
def bfs(rooms, start_v, visited):
# Queue 생성
q = deque()
# 시작점을 Queue에 등록 후 방문 목록에 이에 해당하는 인덱스 초기화
q.append(start_v)
visited[start_v] = True
# Queue에 요소가 있는 동안은 계속 반복
while q:
# 현재의 점을 Queue에서 가장 먼저 들어온 친구 등록 및 제거
cur_v = q.popleft()
# rooms 리스트의 현재 요소에 이어진 친구들을 반복문을 통해서 사용
for next_v in rooms[cur_v]:
# 만약 방문 리스트에 해당 방을 방문한 적이 없으면 Queue에 추가하고 방문 기록을 True로 바꿔준다.
if not visited[next_v]:
q.append(next_v)
visited[next_v] = True
# False가 존재한다면 False
if False in visited:
return False
# 그렇지 않다면 모든 방을 방문 할 수 있다는 말이므로 True
else:
return True
bfs(rooms, 0, visited)
return all(visited)- 1차 코드
from collections import deque from typing import List class Solution: def canVisitAllRooms(self, rooms: List[List[int]]) -> bool: # 방문 리스트 초기화 visited = [False] * len(rooms) # BFS 정의 def bfs(rooms, start_v, visited): # Queue 생성 q = deque() # 시작점을 Queue에 등록 후 방문 목록에 이에 해당하는 인덱스 초기화 q.append(start_v) visited[start_v] = True # Queue에 요소가 있는 동안은 계속 반복 while q: # 현재의 점을 Queue에서 가장 먼저 들어온 친구 등록 및 제거 cur_v = q.popleft() # rooms 리스트의 현재 요소에 이어진 친구들을 반복문을 통해서 사용 for next_v in rooms[cur_v]: # 만약 방문 리스트에 해당 방을 방문한 적이 없으면 Queue에 추가하고 방문 기록을 True로 바꿔준다. if not visited[next_v]: q.append(next_v) visited[next_v] = True # False가 존재한다면 False if False in visited: return False # 그렇지 않다면 모든 방을 방문 할 수 있다는 말이므로 True else: return True
그냥 뭐에 홀린듯이 bfs를 호출을 안했다.. 난 뭘까.. 그래도 배운게 있다!
배우게 된 점
python의 all 함수!
all 함수는 Python 내장 함수로, 주어진 반복 가능한 객체(iterable)의 모든 요소가 True인지 확인한다. 만약 모든 요소가 True이면 True를 반환하고, 하나라도 False가 있으면 False를 반환한다. 이 함수는 리스트, 튜플, 집합, 문자열 등 여러 iterable 객체에 사용할 수 있다.
all([True, True, True]) # 결과: True
all([True, False, True]) # 결과: False
all([]) # 결과: True -> 빈 iterable 객체에 대해서는 항상 True를 반환한다. 이 점은 논리적으로 모든 조건을 만족한다고 볼 수 있기 때문이다.
all((1, 2, 3)) # 결과: True (0이 아닌 모든 숫자는 True로 간주)
all((1, 0, 3)) # 결과: False (0은 False로 간주)
all("abc") # 결과: True (빈 문자열이 아닌 모든 문자는 True로 간주)
all("") # 결과: True (빈 문자열은 True로 간주)
# 문제에서의 사용
# all 함수 사용: visited 리스트의 모든 값이 True인지 확인하여 모든 방을 방문했는지 판단합니다.
return all(visited)++ 0711
BFS, DFS 설명하면서 템플릿 외우기려보다 논리를 이해하고 외우기!!!!!!!! 제발 ㅠ
