0. 문제
'''
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
이러한 미로가 주어졌을 때,
(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.
다음 N개의 줄에는 M개의 정수로 미로가 주어진다.
각각의 수들은 붙어서 입력으로 주어진다.
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.
항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
'''
'''
4 6
101111
101010
101011
111011
>> 15
4 6
110110
110110
111111
111101
>> 9
2 25
1011101110111011101110111
1110111011101110111011101
>> 38
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
>> 13
'''
1. 답
import sys
from collections import deque
sys.stdin = open("input.txt", "r")
# 최단거리 문제는 bfs 로 품!!
def bfs(sx, sy, ex, ey):
# q, v 초기화
q = deque()
v = [[0] * M for _ in range(N)]
# 시작점 큐에 넣고 방문 처리
q.append((sx, sy))
v[sx][sy] = 1
# 큐가 다 빌 때까지 반복
while q:
# 최하단 값 꺼내기
x, y = q.popleft()
# 목적지 여부 확인 및 정답 반환
if (x, y) == (ex, ey):
return v[x][y]
# 4방향 비교 -> 조건 맞으면 큐 삽입 및 방문 처리
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
# 범위 안에 있고, 갈 수 있는 길이며, 아직 방문하지 않은 곳이면
if 0 <= nx < N and 0 <= ny < M and miro[nx][ny] == 1 and v[nx][ny] == 0:
q.append((nx, ny))
v[nx][ny] = v[x][y] + 1
# 하나씩 나눠서 변수에 담기 -> split()
N, M = map(int, sys.stdin.readline().split())
# 한 줄 통째로 받기 -> strip()
# 101111 -> [1, 0, 1, 1, 1, 1]
miro = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
v = [[0 for _ in range(M)] for _ in range(N)]
print(bfs(0, 0, N -1, M -1))
혼자서 풀어보려고 노력해봤지만 잘 안됐다 ㅠ
그래서 해설 영상을 찾아서 보고... 안보고 쳐보는 방식으로 해서 겨우겨우 통과했다.
BFS 문제를 많이 연습해봐야겠다!
그리고 손코딩을 먼저 하도록 습관을 들여봐야겠다.
바로 코드를 치려고 하니까 생각전개도 잘 안되고 막막하고 답답하더라.
물론? 손코딩 해도 뭐가 안되긴 함...
하다보면 어떻게든 손에 익겠지 뭐~
0. 문제
'''
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
이러한 미로가 주어졌을 때,
(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.
다음 N개의 줄에는 M개의 정수로 미로가 주어진다.
각각의 수들은 붙어서 입력으로 주어진다.
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.
항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
'''
'''
4 6
101111
101010
101011
111011
>> 15
4 6
110110
110110
111111
111101
>> 9
2 25
1011101110111011101110111
1110111011101110111011101
>> 38
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
>> 13
'''
1. 답
import sys
from collections import deque
sys.stdin = open("input.txt", "r")
# 최단거리 문제는 bfs 로 품!!
def bfs(sx, sy, ex, ey):
# q, v 초기화
q = deque()
v = [[0] * M for _ in range(N)]
# 시작점 큐에 넣고 방문 처리
q.append((sx, sy))
v[sx][sy] = 1
# 큐가 다 빌 때까지 반복
while q:
# 최하단 값 꺼내기
x, y = q.popleft()
# 목적지 여부 확인 및 정답 반환
if (x, y) == (ex, ey):
return v[x][y]
# 4방향 비교 -> 조건 맞으면 큐 삽입 및 방문 처리
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
# 범위 안에 있고, 갈 수 있는 길이며, 아직 방문하지 않은 곳이면
if 0 <= nx < N and 0 <= ny < M and miro[nx][ny] == 1 and v[nx][ny] == 0:
q.append((nx, ny))
v[nx][ny] = v[x][y] + 1
# 하나씩 나눠서 변수에 담기 -> split()
N, M = map(int, sys.stdin.readline().split())
# 한 줄 통째로 받기 -> strip()
# 101111 -> [1, 0, 1, 1, 1, 1]
miro = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]
v = [[0 for _ in range(M)] for _ in range(N)]
print(bfs(0, 0, N -1, M -1))
혼자서 풀어보려고 노력해봤지만 잘 안됐다 ㅠ
그래서 해설 영상을 찾아서 보고... 안보고 쳐보는 방식으로 해서 겨우겨우 통과했다.
BFS 문제를 많이 연습해봐야겠다!
그리고 손코딩을 먼저 하도록 습관을 들여봐야겠다.
바로 코드를 치려고 하니까 생각전개도 잘 안되고 막막하고 답답하더라.
물론? 손코딩 해도 뭐가 안되긴 함...
하다보면 어떻게든 손에 익겠지 뭐~
