#include <stdio.h>
//bfs로 하면 좋은 점은 dfs는 각 경우의 따라서 어떤 경우가 최소인지 결정해야할 때가 있음
//bfs는 같은 층에 있는 노드들을 쭉 훑고 그 다음 층으로 내려가기 때문에 각 경우가 최소의 해인걸 알 수있음 (애초에 겹치는 경우가 없다, 비교해서 어떤 경우가 최소인지 확인하는 경우가 없음)
int arr[101][101];
int dp[101][101]; //미로 저장
int queue[10001][2]; //방문한 좌표를 저장하여 queue 생성 -> front와 rear을 이용해 문제 해결!
int dx[4]={-1,1,0,0}; // 4가지 방향의 x좌표
int dy[4]={0,0,-1,1};
int bfs(int n,int m)
{
int front=0,rear=0;
queue[0][0]=1; //x좌표!
queue[0][1]=1; //1,1부터 저장해서 n,m까지 들어가게 해야함!
rear++;
while(front<rear) //큐가 빌때까지
{
int x=queue[front][0];
int y=queue[front][1];
front++; //하나 삭제
for(int i=0;i<4;i++)
{
int nx=x+dx[i];
int ny=y+dy[i];
// 미로를 벗어나는 경우
if(nx < 1 || ny < 1 || nx > n || ny > m)
continue;
// 길이 아닌 경우(0인경우)
if(dp[nx][ny] != 1)
continue;
dp[nx][ny]=dp[x][y]+1;
queue[rear][0]=nx;
queue[rear][1]=ny;
rear++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%d ",dp[i][j]);
}
printf("\n");
}
return dp[n][m];
}
int main(void)
{
int y,x;
scanf("%d %d",&y,&x);
for(int j=1;j<=y;j++)
{
for(int i=1;i<=x;i++)
{
scanf("%1d",&dp[j][i]);
}
}
int result=bfs(y,x);
printf("%d",result);
}
#include <stdio.h>
char arr[102][103];
int dp[102][102];
void dfs(char arr[][103],int *depth_max,int depth,int j,int i, int y,int x,int dp[][102])
{
if(j==y && i==x) //(N,M)에 도착!
{
if(dp[j][i]==0)
dp[j][i]=depth; //아직 한번도 안지나감
else
{
if(dp[j][i]>depth)
dp[j][i]=depth;
}
return;
}
if(arr[j][i+1]=='1' && i+1<=x) //오른쪽으로 갈때
{
if(dp[j][i+1]==0)
dp[j][i+1]=depth; //아직 한번도 안지나감
else
{
if(dp[j][i+1]>depth)
dp[j][i+1]=depth;
}
dfs(arr,depth_max,depth+1,j,i+1,y,x,dp);
}
int tmp=*depth_max; // 경우의 수가 2개이므로 저장해뒀다가 생각을 해줘야함
if(arr[j+1][i]=='1' && j+1<=y) //아래로 갈때
{
if(dp[j+1][i]==0)
dp[j+1][i]=depth; //아직 한번도 안지나감
else
{
if(dp[j+1][i]>depth)
dp[j+1][i]=depth;
}
dfs(arr,depth_max,depth+1,j+1,i,y,x,dp);
}
if(arr[j-1][i]=='1' && j-1>=1) //위로 올라감
{
if(dp[j-1][i]==0) //아직 한번도 안지나감, 비효율적으로 간적이 없을때
{
dp[j-1][i]=depth;
dfs(arr,depth_max,depth+1,j-1,i,y,x,dp);
}
}
if(arr[j][i-1]=='1' && i-1>=0) //왼쪽으로 올라감
{
if(dp[j][i-1]==0) //아직 한번도 안지나감, 비효율적으로 간적이 없을때
{
dp[j][i-1]=depth;
dfs(arr,depth_max,depth+1,j,i-1,y,x,dp);
}
}
}
int main(void)
{
int y,x;
scanf("%d %d",&y,&x);
for(int i=1;i<=y;i++)
{
scanf("%s",arr[i]); //이렇게 되면 0부터 index가 채워짐
}
int depth_max=1; //가장 depth가 깊은지 확인
int depth=1;
dp[1][0]=1;
if(arr[1][1]=='1'&&x!=1)
{
dp[1][1]=depth+1;
dfs(arr,&depth_max,depth+2,1,1,y,x,dp);
}
if(arr[2][0]=='1'&&y!=1)
{
dp[2][0]=depth+1;
dfs(arr,&depth_max,depth+2,2,0,y,x,dp);
}
/* for(int j=1;j<=y;j++)
{
for(int i=0;i<x;i++)
printf("%d ",dp[j][i]);
printf("\n");
}*/
printf("%d", dp[y][x-1]);
}