[백준] 2665 미로만들기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

최초 접근시 DFS 이용하여 접근하였으나 배열의 크기로 인하여 시간초과를 예상했습니다.

그래서 BFS 를 사용하여 접근하였습니다.

2) 알고리즘

• BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

def solution():
    q = deque([(0, 0)])             # 시작
    visited[0][0] = 0               # 시작 방문처리

    while q:
        node = q.popleft()
        for k in range(4):
            r = node[0] + dr[k]     # 새로운 좌표
            c = node[1] + dc[k]

            if 0 <= r < N and 0 <= c < N and visited[node[0]][node[1]] < visited[r][c]:     # 다음에 움직일 좌표가 현재 좌표보다 더 많은 방을 바꾸었을 때
                visited[r][c] = visited[node[0]][node[1]]                                   # 다음 좌표는 현재 좌표의 값으로 갱신
                if not board[r][c]:                            # 검은 방이면 바꾸는 횟수 1 증가
                    visited[r][c] += 1
                q.append((r, c))                               # 다음 탐색
                

dr = [-1, 0, 1, 0]                  # 상 우 하 좌
dc = [0, 1, 0, -1]

N = int(sys.stdin.readline())       # 배열의 크기
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]        # 배열 입력
visited = [[1e10] * N for _ in range(N)]                                        # 방문 처리 및 검은방을 몇번 바꿔야하는지 카운트

solution()                      # 탐색

print(visited[N-1][N-1])        # 정답 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2665

2665번: 미로만들기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다.