본문 바로가기

Computer Science/Algorithm

[Algorithm] Grid Challenge

Grid Challenge




[Problem]


소문자로만 이루어진 2차원 배열 G가 있다. 

i행 j열의 원소를 G[i][j]라고 한다.


2차원 배열 G는 소문자로만 이루어져있다.


이 2차원 배열을 가지고 1가지의 연산만을 할 수 있다.

G[i][j]와 G[i][j+1]의 두 원소를 SWAP할 수 있다.


이 때, 주어진 배열 G가 swap연산만을 사용하여 


G[i][1]G[i][2]G[i][N] for 1iN and 
G[1][j]G[2][j]G[N][j] for 


을 만족할 수 있는가? 


[Input Format]

첫 줄에는 총 TestCasts T.

각 테스트 케이스마다 2차원 배열 G의 크기인 N이 주어진다.


이후 N줄에 대해서 배열 G의 원소들이 입력된다.


[Output Format]

주어진 조건을 만족하면  "YES"

만족하지 않으면 "NO"


[Sample Input]


1
5
ebacd
fghij
olmkn
trpqs
xywuv


[Sample Output]

YES


[Solve]


2차원 배열 G가 해당 조건을 만족하는지 알기 위해서, 

1) 각 행에 대해서 bubbleSort를 수행.

2) bubbleSort를 수행한 결과에 대해서 열을 기준으로 조건을 만족하는지 검사.



















'Computer Science > Algorithm' 카테고리의 다른 글

[Algorithm] Sherlock and Array  (0) 2016.04.11
[Algorithm] Snakes and Ladders: The Quickest Way Up  (0) 2016.04.08
[Algorithm] Maximise Sum  (0) 2016.03.25
[Algorithm] Utopian Tree  (0) 2016.03.21
Algorithm 진행 계획  (0) 2016.03.16