문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 192 MB | 199633 | 91214 | 57974 | 44.155% |
문제 설명
N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
4 6
101111
101010
101011
111011예제 출력 1
15예제 입력 2
4 6
110110
110110
111111
111101예제 출력 2
9예제 입력 3
2 25
1011101110111011101110111
1110111011101110111011101예제 출력 3
38예제 입력 4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111예제 출력 4
13풀이과정
문제 아이디어
-
이 문제는 N*M 형태의 미로를 구현하고, 미로의 범위를 조건에 넣는 과정이 중요하다.
- 미로 문제는 처음이라 해당 조건문은 다른사람의 풀이를 참고했다.
# 2차원 형태에서의 bfs 구현
dx = [-1,1,0,0] # 왼쪽 오른쪽
dy = [0,0,-1,1] # 아래 위
for i in range(4):
nx = x + dx[i] # i값이 0==왼쪽, 1==오른쪽
ny = y + dy[i] # i값이 2==아래, 3==위
if nx<0 or nx>=n or ny<0 or ny>=m:
continue # 범위를 넘을 경우 아무것도 안하기- 상하좌우로 탐색을 시도하면서, 만약 x와 y의 좌표가 미로 범위를 넘을 경우엔 탐색을 중단하는 코드는 위와 같다.
if graph[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1 # 방문 처리
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1- 그래프를 탐색하면서 지나왔던 칸 수를 더해 값을 갱신해주는 코드
최종 코드
from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()
n, m = map(int,input().split()) # 미로 크기(n: 행 개수, m: 열 개수)
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
visited = [[0]*(m) for _ in range(n)] # 방문 여부
# 2차원 형태에서의 bfs 구현
dx = [-1,1,0,0] # 왼쪽 오른쪽
dy = [0,0,-1,1] # 아래 위
queue = deque([(0,0)]) # 항상 인덱스 0,0에서 시작
visited[0][0] = 1
def bfs():
while queue:
x, y = queue.popleft()
# 미로의 조건 확인(범위를 벗어나서는 안됨)
for i in range(4):
nx = x + dx[i] # i값이 0==왼쪽, 1==오른쪽
ny = y + dy[i] # i값이 2==아래, 3==위
if nx<0 or nx>=n or ny<0 or ny>=m:
continue # 범위를 넘을 경우 아무것도 안하기
if graph[nx][ny] == 1 and visited[nx][ny] == 0:
visited[nx][ny] = 1 # 방문 처리
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1
return graph[n-1][m-1] # 최종 칸의 개수 반환
print(bfs())-
나의 최종 제출 코드이다.
-
여기서 주의할 점은, 정수형태로 input받은 값을 바로 list에 넣어주기 때문에
input대신sys.stdin.readline을 바로 넣어주면 안된다.sys.stdin.readline은 맨 뒤에 공백을 함께 입력받기 때문. -
따라서
input = lambda : sys.stdin.readline().rstrip()와 같이 입력받아야한다. -
예제1번을 이용해 위 코드를 실행한 결과, 최종 graph의 값은 아래와 같다.
코드 피드백
-
사실 위의 코드에서
visited방문여부를 저장해줄 리스트를 생성했는데, 이는 굳이 작성할 필요가 없다. -
if graph[nx][ny] == 1 and visited[nx][ny] == 0:이 부분에서graph[nx][ny]값이 1이라면 무조건 방문한 적이 없는 좌표이기 때문.- 좌표를 방문함에 따라
graph[nx][ny]값이 직전 좌표에 비해 +1 씩 증가하는데, 이는 방문한적이 있는 좌표일 경우 무조건 값이 1이 아님을 의미한다. 따라서visited[nx][ny] == 0라는 조건은 굳이 추가할 이유가 없다.
- 좌표를 방문함에 따라
from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()
n, m = map(int,input().split()) # 미로 크기(n: 행 개수, m: 열 개수)
graph = []
for _ in range(n):
graph.append(list(map(int,input())))
# 2차원 형태에서의 bfs 구현
dx = [-1,1,0,0] # 왼쪽 오른쪽
dy = [0,0,-1,1] # 아래 위
queue = deque([(0,0)]) # 항상 인덱스 0,0에서 시작
def bfs():
while queue:
x, y = queue.popleft()
# 미로의 조건 확인(범위를 벗어나서는 안됨)
for i in range(4):
nx = x + dx[i] # i값이 0==왼쪽, 1==오른쪽
ny = y + dy[i] # i값이 2==아래, 3==위
if nx<0 or nx>=n or ny<0 or ny>=m:
continue # 범위를 넘을 경우 아무것도 안하기
if graph[nx][ny] == 1:
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1
return graph[n-1][m-1] # 최종 칸의 개수 반환
print(bfs())- visited 부분을 삭제한 위의 코드를 실행해도 정상적으로 출력함
- visited 부분은 불필요하므로 삭제할 경우 메모리와 실행시간에서도 이전 코드보다 효율적으로 작동함을 확인
