만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

공기 누출

면접 대비

시간 제한1초메모리 제한1024 MB

요약
25×25×25 격자의 모듈 사이에 열린 문 목록이 주어질 때, 손상된 모듈로 공기가 흘러드는 모든 모듈을 찾습니다.
난이도

보통10점 중 4점

유형
그래프, BFS
정답자
아직 제출이 없습니다

문제

우주 정거장은 25×25×2525 \times 25 \times 25 격자에 배치된 정육면체 모듈로 이루어져 있다. 각 모듈의 위치는 X, Y, Z 좌표로 나타내며, 좌표값은 1…251 \ldots 25 범위의 정수이다. X, Y, Z 축 방향으로 서로 인접한 두 모듈은 터널로 연결된다. 각 터널의 양 끝에는 문이 하나씩 있다. 두 문이 모두 열려 있으면 두 모듈 사이로 공기가 흐를 수 있다.

모듈 하나가 손상되어 우주 공간으로 공기가 새고 있다. 손상된 모듈로 직접, 또는 다른 모듈을 거쳐 공기가 흘러갈 수 있는 모듈에서도 공기가 빠져나간다. 공기가 빠져나가는 모듈을 모두 찾으시오. 손상된 모듈의 문은 정상적으로 동작한다고 가정해도 된다.

입력

첫 줄에 정거장에서 열려 있는 문의 개수 UU가 주어진다 (1≤U≤10 0001 \le U \le 10\,000). 다음 UU개의 줄에는 열려 있는 문 하나씩에 대해 모듈의 좌표와 문의 방향이 주어진다. 방향은 축 이름 뒤에 좌표가 증가하는 방향이면 '+', 감소하는 방향이면 '-'를 붙여 나타낸다. 마지막 줄에는 손상된 모듈의 좌표가 주어진다.

출력

공기가 빠져나가는 모듈의 좌표를 한 줄에 하나씩 출력한다. Z 좌표 오름차순, 같으면 Y 좌표 오름차순, 그다음 X 좌표 오름차순으로 정렬한다.

예제1

  1. 예제 1

    입력
    5
    2 1 1 X-
    1 1 1 X+
    1 1 1 Z+
    3 1 1 X-
    1 1 2 Z-
    1 1 1
    
    예상 출력
    1 1 1
    2 1 1
    1 1 2