BFS/DFS part - 1

BFS/DFS কি , কিভাবে কাজ করে এই ব্যাপারে আমি আর কিছু লিখতে যাচ্ছি না । অনেক ভাল ব্লগ লেখা হইছে এইটা নিয়ে । এইখানে আমার ইচ্ছা BFS/DFS দিয়ে কিছু interesting problem কিভাবে সল্ভ করা যায় এর solve ট্রিক্স লিখে রাখা । যদি কারো এই এল্গরিথম নিয়ে কোন আইডিয়া না থাকে তাহলে নিচের লিঙ্ক থেকে দেখে নিতে পারে ।

1. BFS 
2. DFS    
3. youtube  

যারা একদমই নতুন নতুন BFS/DFS শিখেছে তাদের এই জন্য লিখাটা খুব একটা উপকারি হবে না । আমি চেস্টা করছি কিছু interesting problem এর solution process বলার জন্য ।

Xor-Tree ::
এই প্রবলেম এ বলা হইছে আমাদের একটা tree input দেওয়া হবে । প্রাথমিক ভাবে এর কোন নোডে কি কি ভ্যালু আছে ( ভ্যালু শুধু মাত্র ১/০ ) আছে তাও দেওয়া আছে । আমাদের একটা টার্গেট প্রসেস এ যাইতে হবে । এইখানে আমরা  কিছু কাজ করতে পারি ।

1.  আমরা চাইলে কিছু নোড এর ভ্যালু ফ্লিপ করে দিতে পারি ( মানে এখন আছে ১ তাহলে হয়ে যাবে ০ , যদি থাকে ০ তাহলে হয়ে যাবে ১ ) 
2. যদি আমরা ফ্লিপ করি তাহলে তার চাইল্ডের চাইল্ড মানে , আমরা এখন যদি থাকি   লেভেল ২ এর কোন নোডে । তাহলে লেভেল ৪ , ৬ , ৮ ......।। নোডের ভ্যালুও ফ্লিপ হবে ।   

আমাকে বলতে হবে আমি মিনিমাম কতটা ফ্লিপ অপারেশন এর মাধ্যমে এখন যেই অবস্থাতে আছি তা থেকে আমি আমার target stage এ  পৌঁছাতে পারব ।
আমরা কিছু সিন্ধান্ত নিতে পারি যেহেতু এইটা একটা ট্রি তাই । 

1.  এইখানে রুট বলা হইছে নোড ১কে ।  রুট থেকে আমি DFS চালাব । 
2. যখনই আমি দেখব আমার কারেন্ট যে ভ্যালু আছে তা আমার টার্গেট ভ্যালু এর সাথে ম্যাচ করছে না তখনই আমি ফ্লিপ করে দিব । যদিও এইটা দেখার আগে আমাকে দেখে নিতে হবে আমার কারেন্ট যে ভ্যালু আছে তার কোন দাদা বা দাদার দাদা এর থেকে তার ভ্যালু এখন ফ্লিপ হচ্ছে কিনা । 
3. কারেন্ট যে ভ্যালু আছে তা ফ্লিপ করতে হবে কি হবে না এইটা বুঝার জন্য আমাকে একটা ভ্যারিএবল রাখতে হবে । 
4. DFS call হবে এইরকম ভাবে DFS( current_node , parent , need_to_flip_now , need_to_flip_my_child )

কোড 

রান টাইম হবে O(node)
Distance in Tree :
এইটা অনেক চমৎকার একটা প্রবলেম । আমাদের একটা ট্রি দেওয়া হবে , আর একটা ভ্যালু K দেওয়া থাকবে , আমাদের বলতে হবে আমরা ট্রিতে কতটা distinct pair of nodes পাব যাদের মধ্যে distance হবে আমার K ।
প্রবলেমটা পড়ে একটু কঠিন মনে হইল এর সমাধান অনেক ইজি । tree dp এর প্রবলেম ও বলে এই ধরনের প্রবলেমকে ।
কিভাবে করর :

1. যেহেতু এইটা রুটেট ট্রি , কোন রুট u হলে , এর দুইটা চাইল্ড v আর w হইলে , তাদের মধ্যে distance হচ্ছে , v - u প্লাস u - w .
2. আমরা খুব সহজেই তাহলে কোন রুট এর দুইটা সাব ট্রি থেকে এর চাইল্ডের মধ্যে k distance এর রিলেশন পেতে পারি । রিলেশনটা হবে
    
          Ans += (  j = 1 to k ) dp[u][j-1] * dp[v][ k - j ]   ;
   এইখানে ,
        ( j - 1 + k - j + distance( u , v )  == k )
3. এখন প্রতিটা সাব ট্রি এর ক্যালকুলেশন এর পর আমার ট্রি এর নোড এর লেভেল আপডেট করব ।   

             ( j = 1 to k ) dp[u][j] += dp[v][j-1] ;

কোড :

এই কোডের রান টাইম হবে O( Node * K ) .

Find Lexicographically Smallest Permutation :
আমাদের এই প্রবলেম এ বলা হইছে আমাদের একটা N সাইজের Array দেওয়া থাকবে । এই array থেকে lexicographically smallest permutation আমাদের প্রিন্ট দিতে হবে কিন্তু এইখানে একটা রেস্ট্রিকশন দেওয়া আছে আমরা চাইলেই যেকোন পজিশন এর ভ্যালু swap করতে পারি না । আমাদের কিছু good position দেওয়া আছে আমরা শুধু মাত্র সেই পজিশন এর মধ্যে ভ্যালু swap করতে পারি ।

Observation 1 :

এইখানে যদি আমরা লক্ষ্য করি complete connected position গুলাতে Array তে যাই ভ্যালু থাকুক না কেন আমরা এই পজিশন গুলার মধ্যে যেহেতু swap করতে পারি ফাইনাল array তে অবশ্যই এই পজিশনগুলার মধ্যে sorted value থাকবে ।

Observation 2:
আমরা যদি এখন observation 1 এর আইডিয়া থেকে array এর উপর dfs চালাই তাহলে আমরা complete connected position গুলার সাথে সাথে আমরা ফাইনাল array তে কি থাকবে তাও পেয়ে যাব ।

এই কোডের রান টাইম কি হবে ? এইটা পাঠকদের উদ্দেশ্যই রেখে দিলাম :D

ইচ্ছা আছে এই সিরিজটা আরো বড় করার । ধন্যবাদ পড়ার জন্য । 

Backtrack & N Queen

[ এইখানের সব চরিত্রই কাল্পনিক , বাস্তবতার সাথে কাছে , উপরে , নিচে , দূরে কোন খানেই কোন মিল নাই । গল্পে তাই বাস্তবতার সাথে কোন মিল ,  কোন লজিক খুঁজে বেড়ানো  অমূলক । ]    

হাতে একটা DLSR আছে আর কোন মেয়ে পটবে না এমনটা হবে না । রেদোয়ান এরও তাই সখিনাকে পটাইতে টাইম লাগল না । স্বাধীনতার পাওয়া থেকে স্বাধীনতা রক্ষা করা কঠিন । এত এত কম্পিটিশন এর যুগে তাই গার্লফ্রেন্ড রক্ষা করা কঠিন । কত কত থ্রেড আনাচে কানাচে । শিশির ভাবুক ছেলে , মনে গভীরের আবেগ বুঝতে তাই দেড়ি হয়ে গেছিল । ভার্সিটির লিফটে মনের আদান প্রদান হইলেও কিঞ্চিৎ সংকোচের কারণে রেদোয়ান এর কাছে একটু পিছিয়ে ছিল । সখিনা আর রেদোয়ান ক্লাসমেট , শিশির তাদের সিনিয়র । নানা ছালচাতুরে রেদোয়ান শিশির কে ধোঁকা দিয়ে সখিনাকে আগলাইয়া রাখলেও বহুমুখী প্রতিভার অধিকারী শিশির যদি কোনভাবেই সখিনার কাছে মনের ভাব পৌঁছাইয়া দিতে পারে , অতি ভাল ফ্রেন্ড থেকে শুধু  ফ্রেন্ড  সম্পর্কে  সখিনা রেদোয়ানকে নামাইয়া নিয়া আসলেও আসতে পারে । তাই কোন ভাবেই রেদোয়ান শিশির এর  কোন প্রকার নোট , হৃদয় দিয়ে আঁকা ছবি সখিনার কাছে পৌঁছাতে দিতে পারে না । এমনেই সহপাঠী বান্ধবী মাত্রই সিনিয়র ভাইয়াদের প্রতি কিঞ্চিৎ দুর্বল থাকে তারপর যদি সিনিয়র বহুমুখী প্রতিভার অধিকারী হয় । বলা রাখা ভাল আমরা এমন একটা যুগের কথা বলতেছি এইযুগে  লিফট , হাতে DLSR থাকলেও মোবাইল ফোন নাই , এমনকি ফেসবুক ও নাই । এই যুগে ছেলে যতই আধুনিক হোক আশে-পাশে  জুনিওর ছেলে থাকলে সৎ সাহস নিয়ে কোন মেয়ের সাথে কথা বলতে সাহস করে না ।  

যেভাবেই হোক রেদোয়ানকে সখিনাকে রক্ষা করতে হবে যেকোন ধরণের আলাপ-চারিতা   শিশির এর কুনজর থেকে । রেদোয়ান ঠিক একটা N*N rectangle Grid কল্পনা করল সখিনার আসে-পাশে একদম দাবা ঘরের মত । এই ঘর গুলা যদি রেদোয়ান গার্ড দিয়ে রাখতে পারে তাহলে শিশির কখনই সখিনার ধারের কাছেও আসবে না ।  রেদোয়ান এর কিছু স্পেশাল ফ্রেন্ড আছে । যারা সব সময় ভাবেই রেদোয়ান এর লাইফে আসে শুধু দুইজন মানুষ , এক সখিনা আর সে । আর কেউ নাই , আর কেউ থাকবে তা ও কল্পনাও করতে পারে না । তারা আবার দাবা খেলার মন্ত্রীর মত গার্ড দিতে পারে । মানে কেউ কোন ঘরে থাকলে মন্ত্রী যেমন এট্যাক করে তেমন করে গার্ড দিয়ে রাখতে পারে সখিনাকে যেন শিশির কোন ভাবেই সখিনার কাছে আসতে না পারে । এমন কিছুটা 

 

ছবির কালো দাগ দেওয়া জায়গা গুলা দিয়া শিশির কোনভাবেই তাই সখিনার সাথে দেখা করতে যাইতে পারে না । কিন্তু এইখানে একটা ঝামেলা আছে । যেহেতু তারা ভাবে এক এবং একমাত্র সখিনা ছাড়া অন্যকেউ ও আর রেদোয়ান এর মাঝে নাই যদি কোন ভাবে তারা জানতে পারে এই সখিনাকে শিশির এর থেকে গার্ড দেওয়ার কামডা রেদোয়ান অন্য আর কাউকেও দিছে তাহলে অনেক কষ্ট পাবে এবং কি ফ্রন্ডশীপ ও আর না থাকতে পারে ।  রেদোয়ান ও আছে তাই  মহাবিপদে , এক শিশির তো আছেই সুযোগ এর সন্ধানে , যখনই সুযোগ পাবে সখিনার সাথে দেখা করে মনের  মহীসোপানের গভীরে যত আবেগ আছে সব প্রকাশ করে দিতে পারে । শেষমেশ রেদোয়ান ঠিক করল , সুপার বুড়া ভাইয়া মাহির এর কাছে প্রবলেম খুলে বলবে ও ।  

সুপার বুড়া ভাইয়া মাহির খুবই গুরু গম্ভীর মানুষ । প্রোগ্রামিং ছাড়া কোন কথা বলেন না । সব কিছু শুনে অনেকক্ষণ চিন্তা ভাবনা করে বলল “ শুন রেদোয়ান তুমি যে প্রবলেম এ আছ , এইডা খুবই পুরাতন ক্যাসিক্যাল N Queen Problem , যা ১৮৫০ সালেই “Franz  Nauck” নামের এক ভদ্রলোক সমাধান দিয়ে গেছেন । এই সমাধান তোমাকে বুঝতে হবে , শুধু বুঝতে হবে না অন্তর দিয়া ফিল ও করতে হবে তাইলেই তুমি সখিনাকে শিশির এর কুনজর থেকে রক্ষা করতে পারবা ”  

আমরা যে যুগে আছি এইডা হইল ভাল যুগ , এইখানে মানুষ মনের মধ্যে ভয়-ভিতি নিয়ে প্রেম-পিরিতি করে কখন কে এসে প্রেমিকা  ভাগাইয়া নিয়া যায় । তাই যতই কঠিন হোক রেদোয়ানকে বুঝতে হবে N-Queen  প্রবলেম এর সমাধান , নিজের জন্য , নিজের অনাগত নাতি-নাতনীর জন্য যে তারা রেদোয়ানকে দাদু , সখিনাকে দিদা ডাকতে পারে ।

N Queen Problem কি ?

N Queen problem হল একটা N*N দাবা বোর্ডে কত ভাবে N টা queen বসানো যায় যাতে তারা একজন অপরজনকে কোন ভাবে এট্যাক না করে । N Queen problem এর solution এর মাধ্যমে আমরা খুব সহজেই যত কম্বিনেশন আছে তা পেয়ে যেতে পারি । 

Solution :  

Queen যেভাবে এট্যাক করে তাতে প্রতিটা Row এবং column এ মাত্র একজন করে queen  বসতে পারে এবং সাথে সাথে আমাদের চেক করে রাখতে হবে diagonal ভাবে কোন Queen আবার যে ঘরে এই Queen টা কে বসাতে চাচ্ছি তাতে  এট্যাক করে   বসে আছে কিনা । কাজটা আমরা খুব সহজেই backtrack দিয়ে করে ফেলতে পারি । আমরা জানি সব Row তে শুধু মাত্রই একটা করে Queen থাকবে এবং সিরিয়ালই যদি আমরা Queen বসাতে থাকি তাহলে আমাদের শুধু বের করতে হবে কোন Queen কোন কলামে আছে যাতে diagonally ও অন্য কোন Queen যেখানে আমরা এই Queenটা বাসাতে চাচ্ছি তাকে এট্যাক করছে না মানে এইখানে আমরা Queen বসাতে পারি ।

একটা জিনিস খেয়াল করি , যখন আমরা কোন Queen বসাই তখন শুধু এইটা চেক করলেই আগের বসানো কোন Queen এর সাথে এখন যে প্লেস এ Queenটা আমরা বসাতে চাচ্ছি তা conflict করছে কিনা মানে এই পজিশন previous বসানো কোন Queen already attack করে রেখেছে কিনা । এইখানে column এর চেক এর পার্টটা অনেক ইজি কিন্তু diagonally part টা একটু tricky . একটা জিনিস খেয়াল করলে দেখা যাবে যে সব কলাম বাম থেকে নিচের ডান দিকে যায় তাদের row আর column এর বিয়োগ ফল একই হয় এবং যে সব কলাম ডান থেকে নিচের বাম দিকে যায় তাদের row এবং column এর যোগফল একই হয় , মানে একটা Queen এর জন্য কলাম সাপেক্ষে দুইটা আলাদা ভাল্যু আছে যেইটা তারা স্টোর করে রাখে যা তাদের অন্য Queen থেকে different করে ।  কোডটা দেখি

এইখানে আমরা global variable column[] , diagonal1[] , diagonal2[] এর মাধ্যমে কোনটা কোনটা নেওয়া হইছে একটা সল্যুশন এর জন্য তা দেখানো হয়েছে । যখন কোন একটা কল হয় তার আগে আমরা এদের ১ করে দিচ্ছি মানে তাদের নেওয়া শেষ , যতক্ষণ পর্যন্ত না recursion কলটা ফেরত আসতেছে ততক্ষণ তারা ১ থাকবে মানে বুক থাকবে । এইভাবে all solution পাওয়া যায় ।

সারাংশ : 

অতপর আমরা এইটা বুঝতে পারি যে যদি আমাদের গার্লফ্রেন্ড রক্ষা করে রাখতে হয় অবশ্যই আমাদের backtrack এর এপ্লিকেশন N Queen সম্পর্কে ক্লিয়ার ধারণা রাখতে হবে নাহলে যুগ যুগান্তর ধরে শিশির এর মত সুযোগ সন্ধানীরা তাদের ভাগাইয়া নিয়া যাবে । UVA 750 প্রবলেমটা এখন তাই করা উচিত সবার ।