✍️오늘 공부한 내용

• 백준 문제 풀이
  • 2178번 미로 탐색
  • 2665번 미로만들기
  • 3055번 탈출
  • 18352번 특정 거리의 도시 찾기

📋새로 배우게 된 내용

• 저번에 함수를 강제 종료하고 싶을 떄 exit(0)를 사용하는데, 언제 쓰나 싶었는데, for문이 중첩되어 있을 때 완전히 for문에서 벗어나고 싶을 때 사용가능하다

for i in graph: #(1)
    for j in i: #(2)
        for k in j: #(3)
            if k == 0:
                print(-1)
                exit(0) #완전 탈출, (1)까지 
            # break # (3) 탈출

• 저번에 bfs, dfs 관련 문제들의 풀이 방식 패턴을 분석해봤는데, 오늘 푼 문제들에도 적용되는지 확인할 수 있는 시간이었다.

😜bfs , dfs 문제 풀이 방식 공통

1. vertex 방문 graph만들어주기
2. 방문여부 그래프 만들어주기
3. edge개수만큼 연결 상태 나타내기
4. 함수 선언하고 vertex인덱스 인자로 받기
5. 큐(bfs) 또는 재귀함수(dfs)로 방문여부 반영
   (추가 분석➕➕)
   ✔️ bfs는 deque를 import해서 leftpop()한 가장 먼저 탐색한 값을 가지고 다음 vertex로 탐색진행을 따지는 경우
   ✔️ dfs는 vertex 하나를 잡고 방문여부를 기준으로 탐색진행을 따지는 경우 (이미 방문을 했다면 재귀빠져나가기)
   ✔️ 다익스트라는 heapq를 import해서 edge가 지닌 weight를 기준으로 우선순위 큐를 활용해서 우선순위를 따지는 경우

• 문제들을 풀다보니 또 하나의 흔한 풀이 방법이 있었는데,
  vertex에서 상하좌우로 움직여야했다면 배열로 움직일 수 있는 범위를 리스트로 만들어주고, range에서 for문을 돌려서 상하좌우일 떄의 조건을 확인해서 큐에 추가여부를 지정할 수 있었다.

🐰2178번 미로탐색 문제 (bfs)

# 상하좌우
dx = [-1, 1, 0, 0] # 현재 좌표 -1,현재좌표 +1로 좌우이동
dy = [0, 0, -1, 1] # 현재 좌표 -1,현재좌표 +1로 상하이동

while queue:
        x, y = queue.popleft() 
        for i in range(4): # 상하좌우 비교 4가지
            nx = x + dx[i]
            ny = y + dy[i]
		# 상하좌우로 이동 시 그래프의 범위 안에서
        # 조건에 맞으면 현재 위치로 설정
        # 해당문제는 이동가능=1, 이동불가능=0인 경우 최소 이동 횟수를 구하는 것
            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1: 
            	# 상하좌우로 이동했던 곳을 현재 위치로
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
                
#### 문제 풀이 전반은 생략, 풀이에 대한 모음은 [백준풀이]에서 따로 다루도록 하겠습니다. ####

🐰2665번 미로만들기 (bfs)

dx = [0, 1, 0, -1] #좌우로 이동
dy = [1, 0, -1, 0] #상하로 이동

 while q: #deque에 값이 있을 때
        x, y = q.popleft() #최초의 푸시값을 가져와서
        if x == N-1 and y == N-1: # 해당문제는 N x N의 그래프에서 끝점인 [N-1][N-1]에 도달하면 미로 완성, N=1인경우 
            return visited[x][y]
            # 그 외에 해당 위치에서 상하좌우로 이동하면서
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            # 그래프 범위를 벗어나지 않으면서 방문하지 않은 지점에 대해
            if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == -1:
            # 상하좌우 움직인 지점이 흰방일 경우
                if arr[nx][ny] == 1:
                # 해당문제는 흰방=1, 검은방=0이고 흰방에서 검은방이동 횟수를 확인하는 문제, 흰방일 때는 그 좌표를 현재로 지정
                    q.appendleft((nx, ny))
                    visited[nx][ny] = visited[x][y]
                else:
                # 검은 방을 만났다면 큐에 넣고 바뀐 횟수도 반영
                    q.append((nx, ny))
                    visited[nx][ny] = visited[x][y] + 1
#### 문제 풀이 전반은 생략, 풀이에 대한 모음은 [백준풀이]에서 따로 다루도록 하겠습니다. ####

🐰7569번 토마토 문제 (bfs)

dx = [-1, 1, 0, 0, 0, 0] #좌우
dy = [0, 0, 1, -1, 0, 0] #상하
dz = [0, 0, 0, 0, 1, -1] # 토마토박스의 높이

while (queue):
    x, y, z = queue.popleft()

    for i in range(6):
        a = x+dx[i]
        b = y+dy[i]
        c = z+dz[i]
        # 상하좌우 윗칸 아랫칸을 이동하면서 해당칸이 익지않은 토마토라면 (graph[a][b][c] == 0) 
        if 0 <= a < h and 0 <= b < n and 0 <= c < m and graph[a][b][c] == 0:
            queue.append([a, b, c]) #큐에 넣기
            graph[a][b][c] = graph[x][y][z]+1 #익으면 1, 토마토가 없으면 -1
#### 문제 풀이 전반은 생략, 풀이에 대한 모음은 [백준풀이]에서 따로 다루도록 하겠습니다. ####

🫥오해했던 점

• 이건 좀 민망(?)할 정도로 어이없는 의문이 들었던 건데,
  bfs로 popleft()하는 코드랑 pop()하는 코드랑 어떻게 다르나 궁금했었다. 같은 문제를 bfs로 각각 pop을 한 경우랑 popleft를 한 경우가 있어서 그럼 pop한 값이 그다지 중요하지 않은가 싶었는데 popleft()를 안하면 굳이 deque를 사용할 필요가 있나 싶기도 했다.
• 결론은 아주아주 큰 착각이었음!😜
• 코드를 자세히 보니 pop을 하기 전에 아예 어떤 값들을 어떤 순서로 push를 해줬냐가 관건이었다. 그리고 break또는 리턴 조건..
  • ex. 큐에 값이 있을 동안에 pop을 계속해주는 함수에서, pop할 값이 n-1,m-1값이고 (n x m 그래프에서), 오른쪽 끝점에 도달할때까지 탐색하는 조건이라면 push했던 값이 0,0이 아니라 list 순서대로 push되어서 n-1,m-1이면 while문이 바로 종료됨.

🤯어려웠던 점

1. 위에도 정리한 패턴(?)에 언급된 사항이기도 한데, 그래프에서 상하좌우를 지정해서 움직일 방법에 대해서 고민을 했었다.

• 첫 생각은 현재 좌표에서 +1,-1을 해주고 해당 좌표를 큐에 담으면 되겠지? 했는데 한 방향으로 이동을 해주고 나서 다른 방향에서 탐색을 어떻게 할 지 고민이 되었다. 아예 큐에 넣지 않고 조건을 만족한 후에 넣어줄까?헀는데 꼬여서 무한루프

2. 큐에 item이 있을 때 while문을 도는데, 이 while문을 끊을 조건이 아직 잘 구현되지 않는다.

😸어려움을 해결한 방법

1. 구글링을 통해 다른 풀이들을 봤었는데,배열로 가능한 이동방향을 만들어주고, 이를 for문으로 돌리고, for문 내에서 조건을 만족하면 큐에 추가해주는 식으로 해주면 된다는 걸 알게 되었다.
2. 아이디어는 어느정도 있는데..방문여부를 체크를 안했다던가 예외처리를 허술하게 했다던가..해서 무한루프에 빠질 때가 종종 있었는데, 아직 100%해결한 문제는 아니다.

• 가능한 줄이는 방법은 if조건들을 if랑 else로 나누는 것보다 elif나 좀 더 상세하게 예외처리를 하도록하는 것
• 중간중간 출력을하거나 디버깅툴을 활용해서 어디가 조건처리가 덜 되었는지 확인해보자.

🤔아쉬웠던 점

• edge관계를 dict 형태로 표현하는식으로 해서 함수를 구성하는 중인데 계속 메모리 초과가 난다. 지금은 할당한 문제 풀이량이 있기 때문에 넘어가야하지만, 다음 문제를 볼 떄는 dict로 구현해봐보자🫡

😝느낀점

• 이제 어느 정도 문제 파악과 함수 작성은 가능해졌는데, 핵심적인 부분인 if조건 (큐에 추가여부를 결정할 조건)에서 좀 막혀서 답답하다. 조급함이 있어서 생각이 잘 안나는 건가
• 방문여부 체크 조건을 뺴먹지 말자! 무한루프에 빠지지말자☠️
• 확실히 어떻게 풀 지, 어떻게 접근할 지 생각을 정리하고 문제들을 보니까 어제보다는 확실히 더 풀리는 느낌이들어서 좋다.

👊다짐

• 조급하게 문제를 맞춘다고 푼게 아니다.
• 모든 문제를 푸는 것보다 한 두 문제라도 내꺼로 만들고 거기서 확장해 나가자.
• 안보고 코드 짤 수 있을 때까지🏃

🚀오늘의 한줄평

• 내꺼하자 bfs,dfs😘