[백준3197] 백조의 호수 (야 한 10번은 다시 봐라)

 

 

 

---

 

BFS(너비 우선 탐색)

BFS를 이용해서 문제해결해야지

 

---

 

 

from sys import stdin
from collections import deque #deque는 양방향 큐, 빠른 큐와 스택 가능

input = stdin.readline  # 입력을 빠르게 받기 위해 사용

dy = (-1, 0, 1, 0)  # 상, 하, 좌, 우 방향/y축은 -1이 상 1이 하 좌우는 y축이 상관 안해서 0
dx = (0, -1, 0, 1)  # 상, 하, 좌, 우 방향

def find_swan(lake, visited, queue):#def는 코드축약=가독성높임/ def 축약할이름(매개변수1,매개변수2,...):
    next_queue = deque() #새로 얼음 녹이는 큐
    while queue: 
        y, x = queue.popleft()#백조의 위치를 차례로 꺼내면서 표시
        if y == swan[1][0] and x == swan[1][1]:#현재1번째 백조 위치가 2번째 백조의 위치와 같을경우
            return True, None #True반환, 끝났으므로 다음은 None

        for ii in range(4):#상,하,좌,우로 이동
            ny = y + dy[ii]#상하
            nx = x + dx[ii]#좌우
            if not 0 <= ny < row or not 0 <= nx < column:#범위확인
                continue #무시
            if visited[ny][nx]:#백조가 방문했던 좌표
                continue#넘어감
            if lake[ny][nx] == 'X':#얼음의 위치에 'X'표시
                next_queue.append((ny, nx))#얼음 위치 탐색할 큐
            else:#얼음 없는 곳
                queue.append((ny, nx))#물 위치
            visited[ny][nx] = True#위에 있는애들 방문했다고 표시하기

    return False, next_queue#백조가 둘이 만나는 곳이 아닌 (물,벗어난범위,얼음) False 따라서 다음 queue으로 넘어감

def melt_ice(water, lake):#얼음이 녹는 과정
    next_water = deque()#새로운 물 위치 저장
    while water:#물이 될 때 까지 반복
        y, x = water.popleft()#물 위치를 큐에서 꺼냄
        for ii in range(4):#상하좌우로 이동하는걸 반복(ii는 방향인덱스)
            ny = y + dy[ii]#새로운 y좌표
            nx = x + dx[ii]#새로운 x좌표
            if not 0 <= ny < row or not 0 <= nx < column:#범위 벗어나면 
                continue#무시
            if lake[ny][nx] == 'X':#얼음이 있는 위치라면
                next_water.append((ny, nx))#물이 될 수 있는 새로운 위치를 next_water에 추거
                lake[ny][nx] = '.'#얼음을 물로 바꿈

    return next_water #얼음을 물로 바꿈

#입력처리
row, column = map(int, input().split())#세로(열)가로(행)크기
lake = []#호수 상태 저장할 리스트
swan = []#백조 위치를 저장할 리스트
water = deque() #물이 있는 위치를 저장할 큐

for rr in range(row):
    current_lake_info = list(input().rstrip())#rstrip(a):a를 삭제한다, 만약 공백이면 오른쪽 공백 사라지게 해줌/호수상태
    for cc, vv in enumerate(current_lake_info):#enumerate:순서있는 데이터 구조 순회/물이 있는 위치 저장
        if vv == '.' or vv == 'L':#vv는 current_lake_info 리스트의 각 요소
            water.append((rr, cc))#물이 있는 좌표 큐에 추가/rr:행, cc:열
        if vv == 'L':#백조가 있는 위치
            swan.append((rr, cc))#백조 좌표를 swan리스트에 저장
    lake.append(current_lake_info)#호수 상태를 lake 리스트에 저장

#백조 탐색 및 이동
day = -1#얼음이 녹을때마다 시간 지나는 변수
visited = [[False for _ in range(column)] for _ in range(row)]#모든 위치 False로 초기화
queue = deque()#백조가 이동할 큐

y, x = swan[0][0], swan[0][1]#첫번째 백조 위치
queue.append((y, x))#첫번째 백조 위치를 큐에 추가
visited[y][x] = True#첫 백조가 방문했다고 표시하기

#얼음 녹이기 및 백조 만남 시 확인
while True:#무한 루프, 다음 조건은 항상 참이므로 계속 반복하라
    day += 1 #시간 지남
    found, next_queue = find_swan(lake, visited, queue)#백조 찾는 함수 돌림
    if found: #만약 return True이면 found도 True 
        break#종료
    water = melt_ice(water, lake)#얼음 녹이는 함수
    queue = next_queue#다음 백조 위치 저장하기 위한 큐 갱신

print(day)#날짜 출력

 

---

코드 정리

<1. 입력받기>

row, column = map(int, input().split())  # 호수의 세로와 가로 크기 입력받기
lake = []  # 호수 상태를 저장할 리스트
swan = []  # 백조 위치를 저장할 리스트
water = deque()  # 물이 있는 좌표를 저장할 큐

 

 

<2.호수상태 입력>

for rr in range(row):#rr은 호수 각 행/호수 상태 입력
    current_lake_info = list(input().rstrip())  # 한 줄씩 호수 상태를 리스트로 변환/rstrip(): 오른쪽부터 ()안 삭제 즉, 공백을 지운다.
    for cc, vv in enumerate(current_lake_info):#cc:열, vv:값 enumerate:정의정리
        if vv == '.' or vv == 'L':  # 물이 있는 위치(.)나 백조가 있는 위치(L)
            water.append((rr, cc))  # 물이 있는 위치를 큐에 추가
        if vv == 'L':  # 백조가 있는 위치
            swan.append((rr, cc))  # 백조 위치를 swan 리스트에 추가
    lake.append(current_lake_info)  # 전체 호수 상태 lake에 저장

 

 

<3. 초기변수 설정>

day = -1  # day추가하는 방법이 day+=1이므로 초기값 -1이다. 만약 day=+1이면 day=0이어야함
visited = [[False for _ in range(column)] for _ in range(row)]  # 모든 방문 여부 false로 초기화.
queue = deque()  # 백조가 이동할 큐

 

<4.백조 이동 시작>

y, x = swan[0][0], swan[0][1]  # 첫 번째 백조 위치
queue.append((y, x))  # 첫 번째 백조위치를 큐에 추가
visited[y][x] = True  # 첫 번째 백조가 방문한 위치 표시

 

<5. 백조가 만날 떄까지 시뮬레이션>

while True:#얼음 녹이기 및 백조 만남 시 확인
    day += 1  # 하루가 지나면 day를 1 증가
    found, next_queue = find_swan(lake, visited, queue)  # 백조가 만났는지 확인
    if found:  # 만약 백조가 만났으면 종료
        break
    water = melt_ice(water, lake)  # 못만나면 melt_ice
    queue = next_queue  # 다음 백조의 이동을 위한 큐 갱신

 

<6. 백조가 만나는 날 출력>

print(day)#최종 흐른 날짜

 

<find_swan: 백조가 서로 만나는지 확인하는 코드>

def find_swan(lake, visited, queue):#백조가 서로 만난지 확인
    next_queue = deque()  # 새로운 백조 위치를 저장할 큐
    
    while queue:  # 백조가 이동할 위치/큐가 비어있지 않으면 계속 진행
        y, x = queue.popleft()  # 큐에서 백조의 현재 위치를 하나씩 꺼냄
        
        # 현재 위치가 두 번째 백조의 위치와 같은지 확인
        if y == swan[1][0] and x == swan[1][1]:
            return True, None  # 백조가 만났으므로 True 반환, 다음 큐는 None
        
        # 상하좌우로 이동하면서 다음 위치를 탐색
        for ii in range(4):  # 상, 하, 좌, 우로 이동
            ny = y + dy[ii]  # 새로운 y 좌표
            nx = x + dx[ii]  # 새로운 x 좌표
            
            # 범위 내에 있는지 확인
            if not 0 <= ny < row or not 0 <= nx < column:
                continue  # 범위를 벗어나면 무시
            
            if visited[ny][nx]:  # 이미 방문한 위치는 무시
                continue
            
            if lake[ny][nx] == 'X':  # 이동할 위치에 얼음이 있는 곳이라면
                next_queue.append((ny, nx))  #next_queue(백조 지나갈 수 있는 위치)에 추가
            else:
                queue.append((ny, nx))  # 물인 곳이라면 백조가 이동할 수 있음
            
            visited[ny][nx] = True  # 백조가 방문한 적 있는 위치 표시
    
    return False, next_queue  # 만약 두 백조가 만나지 않았다면 False와 next_queue 반환

 

<melt_ice: 얼음 녹이는 과정 코드>

def melt_ice(water, lake):#얼음이 녹는 과정
    next_water = deque()#새로운 물 위치 저장
    while water:#물이 될 때 까지 반복
        y, x = water.popleft()#물 위치를 큐에서 꺼냄
        for ii in range(4):#상하좌우로 이동하는걸 반복(ii는 방향인덱스)
            ny = y + dy[ii]#새로운 y좌표
            nx = x + dx[ii]#새로운 x좌표
            if not 0 <= ny < row or not 0 <= nx < column:#범위 벗어나면 
                continue#무시
            if lake[ny][nx] == 'X':#이동 할 위치에 얼음이 있다면 이 얼음은 물 옆의 얼음이므로
                next_water.append((ny, nx))#물이 될 수 있는 새로운 위치를 next_water에 추거
                lake[ny][nx] = '.'#얼음을 물로 바꿈

    return next_water #모든 물 이동 끝나면 next_water 반환

---

질문타임

1. deque사용하는 이유

- list는 맨 앞 데이터 삽입하는데 느림, deque는 빠름 

 

2. if y == swan[1][0] and x == swan[1][1]:

예시) 

백주 1,2가 서로 못 만날 경우

swan = [(1, 2), (4, 5)] 일 때 

현재 백조 위치

1==4 (x) and 2==5(x) 못만남

 

  

---

피드백 환영입니다. 

다들 열공 하세요,,,

나는 이해하는데 4시간 걸림,,, 

바보인거 같기두 하구,,, 어쩌면 집중 했으면 1시간 컷했을텐데,,, 설렁설렁한다고 3시간 낭비한듯,,, 순간 집중력을 길러서 너의 24시간을 아끼자... 아자아자,,, 반성합니다,,,,,