@ [파이썬] [구현] 백준 21608 상어 초등학교

문제

https://www.acmicpc.net/problem/21608

21608번: 상어 초등학교

코드

import sys
input=sys.stdin.readline

dx=[-1,1,0,0]
dy=[0,0,-1,1]

n=int(input())
array=[[0]*n for _ in range(n)]

sati=[[] for _ in range((n**2)+1)]
for i in range(n**2):
    temp=list(map(int, input().split()))
    sati[temp[0]].append(temp[1])
    sati[temp[0]].append(temp[2])
    sati[temp[0]].append(temp[3])
    sati[temp[0]].append(temp[4])

    # 가능한 자리를 담는 임시 배열
    arrayT=[]
    for j in range(n):
        for k in range(n):
            if array[j][k]==0:
                # 좋아하는 친구
                countA=0
                # 빈칸
                countB=0
                for l in range(4):
                    nx=j+dx[l]
                    ny=k+dy[l]
                    if 0<=nx<n and 0<=ny<n:
                       if array[nx][ny] in temp[1:]: countA+=1
                       elif array[nx][ny]==0: countB+=1
                arrayT.append([countA,countB,j,k])
    # 1번째, 2번째 인자는 내림차순으로, 3번째, 4번째 인자는 오름차순으로 정렬해줘!
    arrayT.sort(key = lambda x: (-x[0],-x[1],x[2],x[3]))
    array[arrayT[0][2]][arrayT[0][3]]=temp[0]

result=0
for i in range(n):
    for j in range(n):
        count=0
        for k in range(4):
            nx=i+dx[k]
            ny=j+dy[k]
            if 0<=nx<n and 0<=ny<n:
                if array[nx][ny] in sati[array[i][j]]:
                    count+=1
        result += (10**(count-1)) if count>=1 else 0

print(result)

import java.util.*;
import java.io.*;

public class b21608 {
    // 학생 자리
    static int[][] map;
    // [학생번호][좋아하는 학생 번호]
    static int[][] like;
    static int n;
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};

    static class Info{
        // 좋아하는 학생 수
        int adj;
        // 비어있는 자리 수
        int vac;
        int row;
        int col;

        Info(int adj, int vac, int row, int col){
            this.adj=adj;
            this.vac=vac;
            this.row=row;
            this.col=col;
        }
    }
    
    public static void insert(int person){
        List<Info> info= new ArrayList<>();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(map[i][j]==0){
                    int adjCount=0;
                    int vacCount=0;

                    for(int k=0; k<4; k++){
                        int nx=i+dx[k];
                        int ny=j+dy[k];
                        if(nx>=0 && nx<n && ny>=0 && ny<n){
                            for(int l=0; l<4; l++){
                                if(map[nx][ny]==like[person][l]) adjCount++;
                            }
                            if(map[nx][ny]==0) vacCount++;
                        }
                    }
                    info.add(new Info(adjCount, vacCount, i,j));
                }
            }
        }
        Collections.sort(info, (Info o1, Info o2) -> {
            if(o1.adj==o2.adj){
                if(o1.vac==o2.vac){
                   if(o1.row==o2.row){
                        return o1.col-o2.col;
                    }
                    return o1.row-o2.row;
                   }
                   return o2.vac-o1.vac;
                }
            return o2.adj-o1.adj;
        });

        map[info.get(0).row][info.get(0).col]=person;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int answer=0;

        n=Integer.parseInt(br.readLine());
        map=new int[n][n];
        like=new int[(n*n)+1][4];

        for(int i=0; i<n*n; i++){
            st=new StringTokenizer(br.readLine());
            int person=Integer.parseInt(st.nextToken());
            for(int j=0; j<4; j++){
                like[person][j]=Integer.parseInt(st.nextToken());
            }
            insert(person);
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                int count=0;
                for(int k=0; k<4; k++){
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx>=0 && nx<n && ny>=0 && ny<n){
                        for(int l=0; l<4; l++){
                            if(map[nx][ny]==like[map[i][j]][l]) count++;
                        }
                    }
                }
                if(count>=1) answer+=Math.pow(10, count-1);
            }
        }
        System.out.println(answer);
    }
}

시간 복잡도

(n**4)

 

어려웠던 부분

첫번째 들어가는 학생은 무조건 정중앙으로 들어가야 되는 줄 알았는데, 3번째 조건을 위배한다는 것을 나중에 알았다.