백준 python 7576번 토마토/ 14503번 로봇청소기 / 2206번 벽부수고이동하기

백준 python 7576번 토마토

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

 

Python

from collections import deque
import sys
input = sys.stdin.readline

col, row = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(row)]

visited = [[False] * col for _ in range(row)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
queue = deque()

def Bfs(queue, graph, visited):
    while queue:
        pop_x, pop_y = queue.popleft()

        for i in range(4):
            next_x = pop_x + dx[i]
            next_y = pop_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue
            if not visited[next_x][next_y] and graph[next_x][next_y] == 0:
                queue.append((next_x, next_y))
                visited[next_x][next_y] = True
                graph[next_x][next_y] = graph[pop_x][pop_y] + 1

zero_flag = False
for i in range(row):
    for j in range(col):
        if graph[i][j] == 1:
            queue.append((i, j))

Bfs(queue, graph, visited)

for i in range(row):
    if 0 in graph[i]:
        zero_flag = True
        break

if not zero_flag:
    print(max(map(max, graph)) - 1)
else:
    print(-1)

 

백준 14503번 로봇청소기 

입력
첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

반응형

출력
로봇 청소기가 청소하는 칸의 개수를 출력한다.

 

Python

row, col = map(int, input().split())
x, y, d = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(row)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]  

visited = [[False] * col for _ in range(row)]


def robot(x, y, d, visited):
    clean_count = 1
    turn_count = 0
    while True:
        next_x = x + dx[(d - 1) % 4]
        next_y = y + dy[(d - 1) % 4]
        if not visited[next_x][next_y] and graph[next_x][next_y] == 0: 
            x, y = next_x, next_y
            d = (d - 1) % 4  
            visited[x][y] = True  
            clean_count += 1
            turn_count = 0
            continue
        elif visited[next_x][next_y] or graph[next_x][next_y] == 1:  
            d = (d - 1) % 4
            turn_count += 1

        if turn_count == 4: 
            next_x = x + dx[(d + 2) % 4]
            next_y = y + dy[(d + 2) % 4]
            if graph[next_x][next_y] == 0:
                x = next_x
                y = next_y
                turn_count = 0
            else:
                break
    return clean_count


visited[x][y] = True
print(robot(x, y, d, visited))

 

백준 python 2206번 벽 부수고 이동하기

입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

Python

from collections import deque

row, col = map(int, input().split())
graph = [list(map(int, input())) for _ in range(row)]
visited = [[[0] * 2 for _ in range(col)] for _ in range(row)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def Bfs(start_x, start_y, iscrash, visited, graph):
   
    queue = deque()
    queue.append((start_x, start_y, iscrash))
    visited[start_x][start_y][iscrash] = 1

    while queue:
        cur_x, cur_y, iscrash = queue.popleft()
        if cur_x == row - 1 and cur_y == col - 1:
            return visited[cur_x][cur_y][iscrash]
        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x <= -1 or next_x >= row or next_y <= -1 or next_y >= col:
                continue

            if graph[next_x][next_y] == 0 and visited[next_x][next_y][iscrash] == 0:
                queue.append((next_x, next_y, iscrash))
                visited[next_x][next_y][iscrash] = visited[cur_x][cur_y][iscrash] + 1

            if graph[next_x][next_y] == 1 and iscrash == 0:
                queue.append((next_x, next_y, iscrash + 1))
                visited[next_x][next_y][iscrash + 1] = visited[cur_x][cur_y][iscrash] + 1

    return -1

print(Bfs(0, 0, 0, visited, graph))