sw_1226_미로1

sw_1226 미로1

DFS를 이용해서 미로의 길을 찾는 문제이다.

1. 입력버퍼

2. DFS - 방문했던 곳은 다시 방문하지 않아도 된다.

3. CODE

입력버퍼

cpu가 사용자의 입력을 그때그떄 처리하면 무리가 간다. 그래서 버퍼에 저장하고 있다가 사용자의 입력이 끝나면 데이터를 가져온다. 데이터를 가져오는 함수가 scanf, cin, getline 등 이다.

사용자가 입력을 하면 입력한 문자는 stdin이라는 버퍼에 저장된다. 그리고 '\n' 개행문자를 입력하면 사용자가 입력이 끝났다고 생각하고 scanf함수가 데이터를 cpu로 가져온다.

하지만 만약 scanf("%d", &number); 함수를 호출하면 버퍼에 저장된 '1234592\n' 중 '\n'을 제외한 1234592를 cpu로 가져오게된다 그렇게 되면 다음 줄에 한번더 scanf를 호출하면 stdin 버퍼에 있는 '\n'만 가져오게 된다.

이 문제를 해결하기 위해 다음과 같은 방법을 사용했다.

    ...
    scanf("%d",&test_case);
        for(int i=0;i<16; i++){
            char temp[17];
            scanf("%s ",temp);
            for(int j=0;j<16;j++){
                arr[i][j] = temp[j]- '0';
                visited[i][j] = false;
            }
        }
    ...

Char 배열에 %s로 받아 cpu로 '\n' 까지 읽어들여 버퍼에 '\n'을 없앴다.

DFS - 방문했던 곳은 다시 방문하지 않아도 된다.

방문했던 곳 이기 때문에 다시 함수를 호출하지 않아도 되는데 이 처리를 하지않아 무한 루프를 돌았다.

void solution(int y, int x) {
    ...
        
    if(visited[y][x]) return;
    visited[y][x] = true;

CODE

#include <stdio.h>
#include <iostream>
#include <string>
​
using namespace std;
​
int arr[16][16];
bool visited[16][16];
bool check;
​
​
​
void solution(int y, int x) {
    if(x <0 || y <0 || x>15 || y> 15) return;
    if(arr[y][x] == 1) return;
    if(arr[y][x] == 3) {
        check = true;
    }
    if(visited[y][x]) return;
    
    visited[y][x] = true;
    
    solution(y-1, x);
    solution(y, x-1);
    solution(y+1, x);
    solution(y, x+1);
​
}
​
int main() {
    for(int T = 1;T<11; T++){
        check = false;
        int test_case;
        
        scanf("%d",&test_case);
        for(int i=0;i<16; i++){
            char temp[17];
            scanf("%s ",temp);
            for(int j=0;j<16;j++){
                arr[i][j] = temp[j]- '0';
                visited[i][j] = false;
            }
        }
​
        solution(1, 1);
        
        if(check){
            cout << "#"<< T << " " << 1 << endl;
        }else {
            cout << "#"<< T << " " << 0 << endl;
        }
   
    }
}
​