Educational Codeforces Round 115 (Rated for Div. 2)-A. Computer Game

문제 설명

모노폴리는 컴퓨터게임을 하는 중이다. 모노폴리는 이 게임의 첫번째 단계를 클리어하고 싶다.

첫번째 단계는 $2$개의 행과 $n$개의 열의 격자판으로 이루어져 있는 직사각형이 주어진다. 모노폴리는 $(1, 1)$ 칸에서 출발하는 캐릭터를 조작한다.

모노폴리의 캐릭터는 인접하는 격자나 인접하는 대각선 한칸으로 이동할 수 있다. 즉 엄밀하게 말하자면 캐릭터는 한번에 $(x_1, y_1)$ 에서 $(x_2, y_2)$ 까지 $|x_1 - x_2| \le 1, |y_1 - y_2| \le 1$을 만족하면 이동할 수 있다. 또한 격자 바깥으로는 캐릭터가 움직일 수 없다.

몇개의 칸에는 함정이 있다. 만약 모노폴리의 캐릭터가 함정을 밟으면 캐릭터가 죽고, 게임이 끝난다.

이 게임을 클리어하기 위해서는 모노폴리의 캐릭터는 $(2, n)$으로 이동해야 한다.

모노폴리가 이 단계를 클리어 할 수 있는지 없는지 결정해주자.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 100)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 열의 개수 $n (3 \le n \le 100)$ 이 주어진다.

다음 두 줄에 걸쳐서 단계에 존재하는 격자의 상태가 주어진다. 문자 '0'은 안전한 공간을 의미하고, 문자 '1'은 함정을 의미한다.

추가로 $(1, 1)$ 과 $(2, n)$ 은 항상 안전하다.

Output
각 테스트케이스 마다 단계를 완료할 수 있으면 "YES"를 출력하고 그렇지 않으면 "NO"를 출력한다.

Example
input
4
3
000
000
4
0011
1100
4
0111
1110
6
010101
101010

output
YES
YES
NO
YES

문제 접근

사용한 알고리즘: 그래프 이론, 구현
걸린 시간 : 00:03
딱 보자마자 BFS/DFS를 사용해서 푸는 매우 쉬운 문제라는 것을 알았는데 구현이 잠시 삐끗해서 25분이나 잡아먹은 문제이다. 더욱 골때리는 것은 훨씬 더 쉬운 방법이 있다는 것이었다. 에라이.

문제의 행이 2개밖에 없기 때문에 이런 방법을 사용할 수 있다. 한 열을 기준으로 볼 때, 모두 함정으로 막혀있으면 모노폴리의 캐릭터는 무조건 움직일 수 없다. 즉 반대로 말하자면 한 열에 있는 두 칸 중 하나라도 안전한 구역이 있으면 캐릭터는 반드시 다음 열로 움직일 수 있다.

따라서 한 열씩 차례로 검사를 하면서 1이 두개 있는 경우는 바로 "NO"를 출력하게 하고, 끝까지 모두 검사를 완료하면 단계를 완료할 수 있다는 뜻이므로 "YES"를 출력한다.

정답 코드

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        bool flag = false;
        int n; cin >> n;
        string a, b; cin >> a >> b;
        for(int i = 0; i < n; i++) flag |= (a[i] == '1' && b[i] == '1');
        cout << (flag ? "NO" : "YES") << "\n";
    }
    return 0;
}