[도시와 비트코인/S3/Python3/C++]

31575번 도시와 비트코인 S3

 

문제
전날에 비해 비트코인의 시세가 백만 원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고 한다. 현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다. 도시는 가로 N, 세로 M 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다. 도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다.진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다. 진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성하여라. 진우의 현재 위치가 거래소일 수 있다.

입력
첫 번째 줄에 도시의 가로 크기 N과 세로 크기 M (1≤N,M≤300)이 주어진다. 두 번째 줄부터 M개의 줄에는 도시의 형태를 나타내는 N개의 정수가 공백을 사이에 두고 주어진다. 각 칸이 1인 경우 진우가 갈 수 있는 칸을 의미하고 0인 경우 진우가 갈 수 없는 칸을 의미한다.왼쪽 위의 끝 칸과 오른쪽 아래의 끝 칸은 모두 1이다.

출력
첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

 

 

다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

그래프 탐색 중 아래 및 우측으로만 이동 가능한 문제이다.

너비 우선 탐색을 이용하여 풀이하였다.

 

 

import sys
from collections import deque

row, col = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(col)]

dq = deque([[0, 0]])

move_list = [[1,0],[0,1]]
visit = [[False] * row for _ in range(col)]
visit[0][0] = True

while dq:
    y, x = dq.popleft()

    for ay, ax in move_list:
        dy, dx = y+ay, x+ax
        if dy<0 or dx<0 or dy>=col or dx>=row: continue
        if visit[dy][dx] or maps[dy][dx] == 0: continue
        dq.append((dy, dx))
        visit[dy][dx] = True

print("Yes" if visit[-1][-1] else "No")

 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int maps[301][301];
bool visit[301][301];

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int row, col; cin>>row>>col;
    for (int i=0; i<col; ++i)
    {
        for (int j=0; j<row; ++j)
        {
            int v; cin>>v;
            maps[i][j] = v;
        }   
    }


    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    visit[0][0] = true;

    while (!q.empty())
    {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();

        for (int ay=1; ay>=0; --ay)
        {
            int ax = 1-ay;

            int dy = y+ay;
            int dx = x+ax;
            if (dy<0 || dx<0 || dy>=col || dx>=row) continue;
            if (maps[dy][dx] == 0 || visit[dy][dx]) continue;

            q.push(make_pair(dy, dx));
            visit[dy][dx] = true;
        }
    }

    cout<<(visit[col-1][row-1] ? "Yes" : "No");
}

---